  We study the query complexity of quantum learning problems in which the
oracles form a group $G$ of unitary matrices. In the simplest case, one wishes
to identify the oracle, and we find a description of the optimal success
probability of a $t$-query quantum algorithm in terms of group characters. As
an application, we show that $\Omega(n)$ queries are required to identify a
random permutation in $S_n$. More generally, suppose $H$ is a fixed subgroup of
the group $G$ of oracles, and given access to an oracle sampled uniformly from
$G$, we want to learn which coset of $H$ the oracle belongs to. We call this
problem coset identification and it generalizes a number of well-known quantum
algorithms including the Bernstein-Vazirani problem, the van Dam problem and
finite field polynomial interpolation. We provide character-theoretic formulas
for the optimal success probability achieved by a $t$-query algorithm for this
problem. One application involves the Heisenberg group and provides a family of
problems depending on $n$ which require $n+1$ queries classically and only $1$
query quantumly.
