What BQP Actually Contains: A Taxonomy of Quantum Speed-ups — Epoche C2
The class, and what its definition actually requires $\mathsf{BQP}$ — bounded-error quantum polynomial time — is the complexity class in which the popular claim that quantum computers are faster has to be cashed out, and this essay sorts the speed-ups actually known into four kinds according to the mathematical property each one exploits. The classification, rather than any single algorithm, is what settles the matter: once one sees that nearly every superpolynomial separation on the books comes from a single narrow mechanism, the honest version of the slogan writes itself. A language $L$ is in $\mathsf{BQP}$ if there is a family of quantum circuits $\{C_n\}$ of size polynomial in $n$ such that for every input $x$ of length $n$, measuring the first output qubit of $C_n$ applied to $|x\rangle|0^m\rangle$ gives the correct membership answer with probability at least $2/3$. Three clauses in that sentence do real work. The family must be uniform — a deterministic polynomial-time machine, given $1^n$, must print the description of $C_n$ — since circuit families are otherwise non-uniform objects that could encode one bit of an undecidable set per input length. The gate set is immaterial, by the Solovay–Kitaev theorem: any finite set closed under inverses and generating a dense subgroup of the relevant special unitary group approximates an arbitrary gate to accuracy $\varepsilon$ using $O(\log^{c}(1/\varepsilon))$ gates. And the $2/3$ is arbitrary: majority vote over $k$ runs drives the error below $2^{-\Omega(k)}$, so any constant bounded away from $1/2$ names the same class. Two containments are proved rather than conjectured, and the proofs say what a quantum computation is from a classical point of view. The amplitude assigned to a final basis state is a sum over computational paths through the basis: $$\langle y|U_T U_{T-1}\cdots U_1|x\rangle \;=\; \sum_{z_1,\dots,z_{T-1}} \langle y|U_T|z_{T-1}\rangle\cdots\langle z_2|U_2|z_1\rangle\langle z_1|U_1|x\rangle ,$$ each $z_t$ ranging over all $2^m$ basis states. There are exponentially many terms, but each is a product of $T$ entries of gates acting on $O(1)$ qubits, hence computable in polynomial time; and since there are at most $2^{\mathrm{poly}(n)}$ terms while the probabilities to be distinguished differ by a constant, $\mathrm{poly}(n)$ bits of precision per term suffice. Enumerate the paths in order, accumulate a running sum, reuse the same workspace: the space cost is one path index plus one partial sum, where the obvious state-vector simulation would hold $2^m$ amplitudes at once. That is Bernstein and Vazirani's argument for $\mathsf{BQP}\subseteq\mathsf{PSPACE}$. The path sum wastes its sign structure, and exploiting it gives more. $\mathsf{PP}$ is the class of languages defined by the sign of a $\mathsf{GapP}$ function — the difference between the accepting and rejecting path counts of a nondeterministic polynomial-time machine — and Adleman, DeMarrais and Huang showed in 1997 that a quantum circuit's acceptance probability is such a difference divided by a power of two, giving $\mathsf{BQP}\subseteq\mathsf{PP}$. Since $\mathsf{PP}\subseteq\mathsf{PSPACE}$, that subsumes the previous containment. In the other direction $\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}$, since Toffoli gates make any classical circuit reversible at polynomial overhead and Hadamard gates on ancillas supply unbiased coin flips. Whether $\mathsf{NP}\subseteq\mathsf{BQP}$ is open. So — and this is routinely elided — is whether $\mathsf{P}\neq\mathsf{BQP}$: proving that separation would immediately prove $\mathsf{P}\neq\mathsf{PSPACE}$, open since the class was defined. Every claim of quantum advantage therefore rests on unproven separations, and what follows is a taxonomy of conjectures with unequal evidence behind them. A taxonomy of the speed-ups The sorting principle is the mathematical property of the problem that the machine exploits, not the application area, because that is the variable which predicts whether a newly proposed problem will yield. In the third column the gain sets the best known quantum cost against the best known classical cost for the same problem — upper bound against upper bound, and hence revisable, except in row II, where both bounds are theorems. Class Mechanism Size of the gain Examples I. Hidden structure quantum Fourier transform over an abelian group superpolynomial Shor's factoring and discrete logarithm; Simon's problem II. Amplitude amplification rotating amplitude towards marked items quadratic, and provably no better Grover search; many quantum walks III. Simulation a quantum system simulating a quantum system exponential over known classical methods, for dynamics Hamiltonian time evolution IV. Sampling producing samples, not answering a question evidence of hardness, not a decision result boson sampling, random circuit sampling Class I: what hidden structure means, and where it stops Class I holds the superpolynomial separations, and its mechanism is cleanest in the earliest example. Simon's problem, published in 1994, supplies a black box computing $f:\{0,1\}^n\to\{0,1\}^n$ under the promise that $f(x)=f(y)$ exactly when $y=x\oplus s$ for one fixed unknown non-zero string $s$, which is to be found; classically this is a collision hunt among $2^n$ values, and the birthday bound forces $\Omega(2^{n/2})$ queries. The quantum algorithm queries in superposition and measures the output register, collapsing the input register to $\tfrac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)$ with the offset $x_0$ uniformly random and unknown. A Hadamard on each qubit then gives $|y\rangle$ the amplitude $$\frac{(-1)^{x_0\cdot y}}{\sqrt{2^{n+1}}}\Big(1+(-1)^{s\cdot y}\Big),$$ which vanishes unless $s\cdot y=0$ over $\mathbb{F}_2$. The measurement returns a uniformly random vector orthogonal to $s$; that complement has dimension $n-1$, so $n-1$ independent samples fix $s$ by Gaussian elimination. Notice exactly what the interferenc