Quantum query complexity of symmetric oracle problems

Abstract

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.

v2 25 pages, fixed proof of Prop. 5.6, added Section 7 v3 32 pages, added detail to proofs in Sec. 5, also minor revisions and corrections

References in corpus (3)

• Quantum algorithm for multivariate polynomial interpolation
• Optimal quantum algorithm for polynomial interpolation
• Quantum Oracle Classification - The Case of Group Structure

Cited by in corpus (1)

• Quantum query complexity with matrix-vector products