
In this paper, we analyze the query complexity of the general coset identification problem. We
prove that nonadaptive algorithms are optimal for any coset identification problem. We provide
tools to reduce the analysis of query complexity to purely character theoretic questions (which
are themselves often combinatorial). In particular we derive a formula for the exact quantum
query complexity for coset identification in terms of characters. In the case of symmetric oracle
discrimination (which itself includes polynomial interpolation as a special case) we find the lower
and upper bound for bounded error query complexity.
Another motivation for our work is the study of nonabelian oracles. Much is known about
quantum speedups when the oracle is a standard Boolean oracle. Less is known about whether
oracle problems with nonabelian symmetries can offer notable speedups. To that end we study the
follow scenario: suppose a group G acts by permutations on a finite set Ω (we call Ω a G-set). A
learner is given access to a machine which takes an element ω ∈ Ω and returns a·ω for some hidden
group element a ∈ G. With as few queries as possible the learner should guess the hidden element
a ∈ G. The classical query complexity for this problem is a long-known invariant of G-sets called
the base size. For instance, if G is the full permutation group of Ω = {1, . . . , n} then n −1 queries
are required classically to determine the hidden permutation. This problem is a special case of
symmetric oracle discrimination and we can express the bounded error quantum query complexity
of this purely in terms of the character of the G-set Ω. For instance, we find that when G is the full
permutation group of X = {1, . . . , n} then n−2
√
n+Θ(n
1/6
) queries are necessary (and sufficient)
to determine the hidden element.
This result bears some similarity to other work on learning problems related to the symmet-
ric group. Aaronson and Ambainis [AA14], who prove that at most a polynomial speedup can
be achieved in computing functions on n inputs which are invariant under the action of the full
symmetric group S
n
(using a standard evaluation oracle). Ben-David [BD16] proves that at most
a polynomial speedup is possible for Boolean functions defined on the full symmetric group. More
recently, Dafni, Filmus, Lifshitz, Lindzay and Vinyals [DFL
+
21] have studied the query complex-
ity of Boolean functions defined on the symmetric group, again proving a polynomial relationship
between the quantum and classical query complexities (as well as numerous other complexity mea-
sures). These results may be compared to the well-known fact that only polynomial speedups are
possible in computing total Boolean functions [BBC
+
01], the idea being that learning problems
on the full symmetric group correspond to total functions, while learning problems on a subgroup
correspond to partial functions. All of the results mentioned above are not directly comparable to
ours, since they use a standard evaluation oracle, while we examine a more symmetric “in-place”
oracle model.
The task of oracle identification can be further refined: fix a group G, a G-set Ω, and a func-
tion f : G → X which is constant on left cosets of some subgroup H, and distinct on distinct
cosets. The (left) coset identification problem is to determine f(a) given access to a permutational
black-box hiding a through the action on Ω. For instance, when G = S
n
(the symmetric group),
Ω = {1, . . . , n} its defining representation and f the sign homomorphism, it requires n −1 classical
queries to determine f(a). As a counterpoint to the harsh lower bound above we provide a family
of examples for this task parametrized by n in which the quantum query complexity is 1 while the
classical complexity is O(n). The groups we use are Heisenberg groups acting as small subgroups of
the full permutation group. This example is a nonabelian analogue of the fact that good quantum
speedups can be found in computing partial Boolean functions [BV97].
The paper is organized as follows. In section 2 we formalize coset identification in the context
of quantum learning algorithms and review the notions of adaptive and nonadaptive learning. In
section 3 we prove that parallel queries suffice to produce an optimal algorithm for this task. Sec-
tion 4 applies this theorem to symmetric oracle discrimination and addresses numerous example
problems. In section 5 we return to the general coset identification task and we prove the main
Accepted in Quantum 2021-03-03, click title to verify. Published under CC-BY 4.0. 2