The Complexity Class BQP

A language $L \subseteq \{0,1\}^*$ is in BQP if there exists a polynomial-time uniform family of quantum circuits $\{Q_n\}_{n \ge 0}$, where $Q_n$ acts on $\text{poly}(n)$ qubits and is built from gates in some fixed finite universal gate set, such that for every input $x$ of length $n$: the circuit $Q_n$ takes $x$ (encoded in some standard basis states) together with ancilla qubits initialized to $|0\rangle$, applies $Q_n$, measures a designated output qubit in the computational basis, and accepts if the outcome is 1. The acceptance probability must satisfy

"Uniform" means there is a single deterministic classical polynomial-time algorithm (a Turing machine) that, given $n$ in unary, outputs a description of the circuit $Q_n$ as a list of gates. This uniformity condition is essential: without it, "one circuit per input length" would let each $Q_n$ hard-code the answer for every length-$n$ input, collapsing the class into something unconditionally undecidable-strong (analogous to how non-uniform circuit families capture P/poly rather than P). The classical control that generates the circuit description, feeds in the input, and interprets the measurement outcome is what makes BQP a genuinely algorithmic class, not merely a statement about the existence of unitary matrices. The constants $2/3$ and $1/3$ are not sacred. Any pair of constants $p_{\text{acc}} > p_{\text{rej}}$ with an inverse-polynomial (or even inverse-exponential, up to the gap not vanishing too fast) gap defines the same class BQP, because of an amplification argument analogous to the one used for BPP. Likewise, the specific finite gate set (Hadamard, CNOT, and a phase gate, say, versus Toffoli and Hadamard) does not matter, by the Solovay–Kitaev theorem, which shows any universal gate set can efficiently approximate any other universal gate set's operations to exponential precision using only polylogarithmic overhead. These two robustness facts are what elevate BQP from "a definition" to "the right definition" — a genuine complexity class rather than an artifact of modeling choices.

Anatomy of a BQP computation

A BQP computation on input $x$ of length $n$ proceeds in five stages. 1. Classical preprocessing. A polynomial-time Turing machine, given $1^n$, outputs the description of circuit $Q_n$: a sequence of $\text{poly}(n)$ gates from a fixed universal set, each gate specified by which qubit(s) it acts on. 2. State preparation. Allocate $m = \text{poly}(n)$ qubits. Load $x$ into the first $n$ qubits via basis encoding ($|x_1\rangle \otimes \cdots \otimes |x_n\rangle$); initialize the remaining $m-n$ ancilla qubits to $|0\rangle$. 3. Unitary evolution. Apply the gates of $Q_n$ in sequence, producing the final state $|\psi_x\rangle = Q_n\,(|x\rangle \otimes |0\rangle^{\otimes(m-n)})$. 4. Measurement. Measure a designated output qubit in the computational basis, obtaining outcome $b \in \{0,1\}$ with probability $|\langle b | \psi_x\rangle|^2$ (marginalizing over the other qubits). 5. Decision. Accept if $b=1$, reject if $b=0$. The acceptance probability must respect the $2/3$–$1/3$ gap above. Because a single run is a Bernoulli trial with unknown but gap-separated bias, one cannot trust a single measurement — a rare unlucky outcome could flip the answer. This is where amplification enters, and it is the technical heart of why BQP is a robust, exponentially reliable class despite each individual circuit run being only "somewhat" reliable.

The amplification argument

Suppose $Q_n$ decides $L$ with the $2/3$–$1/3$ gap. Build a new circuit $Q_n'$ that runs $k$ independent, fresh copies of $Q_n$ (fresh ancillas each time, same input $x$), obtains $k$ classical bits $b_1,\dots,b_k$, and outputs the majority bit. Independence across repetitions is what licenses the use of standard tail bounds. Let $p = \Pr[Q_n \text{ accepts } x]$. If $x \in L$, $p \ge 2/3$; if $x \notin L$, $p \le 1/3$. In either case, "majority is wrong" is the event that a Binomial$(k,p)$ random variable lands on the wrong side of $k/2$. Using a Chernoff bound, the probability that the majority is wrong is at most $e^{-c k}$ for a constant $c>0$ depending on the gap ($c$ is on the order of $(2/3-1/2)^2 \cdot 2 \approx 0.055$ by a standard multiplicative Chernoff estimate, though the exact constant is not important — only that it is a positive constant independent of $n$). Choosing $k = O(\text{poly}(n))$, e.g. $k = O(n)$, drives the error probability down to $2^{-\Omega(n)}$, which is more than enough to union-bound over all inputs of length $n$ or to compose polynomially many BQP subroutines. This argument is identical in spirit to amplification for BPP; the only quantum-specific subtlety is that intermediate quantum states from different repetitions must not be allowed to interfere — hence "fresh ancillas" and a purely classical majority vote after measurement, not a coherent combination of the runs.

Closure and composition

Because BQP circuits are compositions of unitaries interspersed only with a final measurement, BQP is closed under polynomial-time Turing reductions with BQP oracles in the sense of bounded-error “post-amplification” composition: if $L_1 \in \text{BQP}$ and $L_2$ has a polynomial-time reduction to $L_1$ that calls the BQP subroutine a polynomial number of times, the errors of the individual calls can each be amplified to exponentially small before composing, and a union bound over the polynomially many calls still yields overall bounded error. This is the same "error budget" technique used throughout randomized and quantum algorithm design. ```text PSEUDOCODE: BQP decision procedure with amplification Input: x, |x| = n; access to universal gate set G; error target ε = 2^-n 1. k ← ceil( C · n ) // C chosen from Chernoff bound so that // Pr[majority wrong] ≤ ε 2. votes ← 0 3. for i = 1 to k: 4. allocate fresh register R_i of poly(n) qubits, initialize to |0...0> 5. load x into the input sub-register of R_i 6. apply circuit Q_n (built by classical uniform generator) to R_i 7. measure the designated output qubit of R_i, obtaining bit b_i 8. votes ← votes + b_i 9. if votes > k/2: 10. return ACCEPT 11. else: 12. return REJECT ``` The outer loop (lines 3–8) is classical control orchestrating $k$ independent quantum sub-executions; only lines 4–7 involve genuinely quantum resources. This separation — classical polynomial-time control wrapping bounded-error quantum subroutines — is exactly what the formal definition of BQP requires and exactly what makes robustness theorems provable: any statement about "the" quantum resource is really a statement about circuit $Q_n$, and classical amplification machinery around it is untouched by changes to the underlying gate set.

Time and space. By definition, each circuit $Q_n$ has size $\text{poly}(n)$ (number of gates), and generating its description takes classical time $\text{poly}(n)$. Amplification multiplies the circuit size by $k = O(n)$, still polynomial, and the majority vote over $k$ bits takes classical time $O(k) = O(n)$. So the total time for the amplified decision procedure — classical generation, quantum execution (counted as one time step per gate, per the standard cost model), and classical vote — is $\text{poly}(n)$. Space is likewise polynomial: $\text{poly}(n)$ qubits per run, reused across the $k$ repetitions (or $k \cdot \text{poly}(n) = \text{poly}(n)$ qubits if run in parallel), plus $O(\log k) = O(\log n)$ classical bits to tally votes.

Correctness of the amplification lemma. Let $X_i$ be the indicator that repetition $i$'s outcome $b_i$ agrees with the "correct" bias direction (i.e., $X_i = b_i$ when $x \in L$, since we want accepts to dominate). The $X_i$ are i.i.d. Bernoulli($p$) with $p \ge 2/3$ (case $x \in L$) or the complementary analysis with $p \le 1/3$ (case $x \notin L$). By the multiplicative Chernoff bound, for i.i.d. Bernoulli variables with mean $p$,

where $D$ is the relevant KL-divergence-type rate function, which is a strictly positive constant whenever $p > 1/2$ is bounded away from $1/2$ — exactly the situation guaranteed by the $2/3$–$1/3$ gap. Concretely, one standard bound gives $\Pr[\text{majority wrong}] \le e^{-2k(p-1/2)^2} \le e^{-2k/36} = e^{-k/18}$ for $p \ge 2/3$. Setting $k = 18n$ gives error at most $e^{-n}$, which is doubly exponentially better than what is needed and leaves ample room for union bounds over subroutine calls.

Why this is not circular. The key subtlety is that this argument requires the $k$ repetitions to be probabilistically independent, which holds because each repetition uses fresh ancilla qubits and no entanglement is shared between repetitions — the only interaction between runs happens classically, after measurement, in the vote. If repetitions shared quantum state, interference effects could in principle correlate outcomes in ways that break the Chernoff analysis; the "fresh ancilla, measure, then classically combine" discipline is what keeps the probabilistic argument valid.

Robustness to gate set changes. The Solovay–Kitaev theorem states that any single-qubit gate can be approximated to precision $\varepsilon$ using $O(\log^{c}(1/\varepsilon))$ gates from any other fixed universal gate set (with $c \approx 3$ in early proofs, later improved). Applying this gate-by-gate to a poly-size circuit $Q_n$ built from gate set $G_1$ yields an equivalent circuit built from gate set $G_2$ of size $\text{poly}(n) \cdot \text{polylog}(1/\varepsilon)$, still polynomial provided $\varepsilon$ is taken to be, say, $1/\text{poly}(n)$ or even $2^{-\text{poly}(n)}$ (the polylog keeps the blowup controlled). Since a per-gate approximation error of $\varepsilon$ accumulates to at most $O(\text{poly}(n)\cdot \varepsilon)$ total variation distance in the output distribution (a standard union-bound-style error accumulation argument for sequences of unitaries), choosing $\varepsilon$ inverse-polynomially small keeps the acceptance-probability gap intact. Hence BQP is unchanged by the choice of universal gate set — the class is a property of what is computable, not of which specific quantum logic gates are provided.

Containment BPP ⊆ BQP. Any BPP machine flips $\text{poly}(n)$ random coins and then runs a deterministic polynomial-time algorithm on the input and the coin flips. A quantum circuit can simulate this: apply a Hadamard gate to each of $\text{poly}(n)$ fresh ancilla qubits to produce a uniform superposition, "measure" them (or equivalently, since the deterministic classical circuit that follows is reversible-simulable, apply the deterministic computation coherently and only measure the final output qubit) to obtain uniformly random bits, and then simulate the deterministic polynomial-time circuit reversibly (every classical circuit can be made reversible with polynomial overhead using Toffoli gates and ancillas, e.g. via the standard technique of computing and then "uncomputing" garbage). The output bit is measured exactly as the BPP algorithm's output bit would be. Since the constructed quantum circuit reproduces the exact same probability distribution over accept/reject as the original BPP machine, the $2/3$–$1/3$ gap transfers directly. This gives BPP ⊆ BQP; the containment is believed (though not proven) to be strict, since problems like integer factorization admit efficient quantum algorithms with no known classical polynomial-time algorithm.

Containment BQP ⊆ PSPACE. The output acceptance probability of a circuit $Q_n$ on input $x$ is

and expanding the unitary $Q_n = U_T \cdots U_1$ as a product of $T = \text{poly}(n)$ local gates, each amplitude $\langle z | Q_n | x0\cdots0\rangle$ can be written as a sum over all possible intermediate computational-basis "paths" $z_0 = x0\cdots0, z_1, \dots, z_{T-1}, z_T = z$ through the $m$-qubit Hilbert space:

Each factor $\langle z_i | U_i | z_{i-1}\rangle$ is a matrix entry of a local gate (acting on $O(1)$ qubits), hence computable exactly (as a ratio of small integers times a bounded number of square roots, or to sufficient precision in polynomial time) using $\text{poly}(n)$ space. The sum has $2^{m(T-1)}$ terms, exponentially many, but a PSPACE machine does not need to enumerate them all simultaneously — it performs the sum via depth-first recursion, maintaining only the current partial path (using $O(mT) = \text{poly}(n)$ bits of space to store the recursion stack) and accumulating the running total to sufficient precision, reusing space as it backtracks. This shows $p(x)$ is computable to inverse-exponential precision in polynomial space, and since deciding "$p(x) \ge 2/3$ vs. $p(x) \le 1/3$" is then just a polynomial-space computation followed by a threshold comparison, BQP ⊆ PSPACE.

Honesty about the gap. These two containments are unconditional theorems. What remains open is exactly how much room exists between them: whether BQP ⊆ P (would mean quantum computers give no super-polynomial speedup for decision problems — widely disbelieved given Shor's algorithm's evidence, but not disproven unconditionally), whether BQP and NP are incomparable (the current default belief, since Grover-type arguments give oracle separations but no unconditional proof for the unrelativized classes), and whether BQP is strictly below PSPACE (almost certainly yes, since collapsing them would have dramatic, unbelieved consequences, but again unproven). BQP's containments are proofs; BQP's exact place relative to NP is a research frontier discussed elsewhere.

We trace amplification concretely for a hypothetical BQP circuit $Q_n$ deciding membership of $x$ in some language $L$, where a single run has acceptance probability $p = 0.7$ when $x \in L$ (comfortably above $2/3 \approx 0.667$).

Reading the table: even though a single circuit run is only "somewhat" better than a coin flip's worth of signal above the threshold, majority voting over a linear number of independent repetitions drives the error down exponentially. This is the same qualitative phenomenon as amplification for randomized algorithms (e.g., repeated Miller–Rabin primality tests), transplanted into the quantum setting with the extra care that repetitions must be quantum-mechanically independent (fresh ancillas, no shared entanglement) for the Chernoff argument to apply cleanly. A second worked case illustrates the PSPACE simulation concretely on a toy 2-qubit circuit. Let $Q$ consist of a Hadamard on qubit 1, then a CNOT with qubit 1 as control and qubit 2 as target, applied to input $|00\rangle$ (this is the standard Bell-state preparation circuit). We want $p = \Pr[\text{measuring qubit 2} = 1]$.

Summing $|{\text{amplitude}}|^2$ over final paths $z_2$ with qubit 2 equal to 1 (only $z_2 = 11$ qualifies): $p = |1/\sqrt2|^2 = 1/2$. A depth-first PSPACE procedure computes exactly this: recurse over the two branches at the Hadamard step, apply the deterministic CNOT transition at each leaf, accumulate $|\text{amplitude}|^2$ for leaves matching the output condition, and never needs to store more than the two live branches' running products at once — space stays proportional to circuit depth times qubit count, not to the exponentially many total paths.

The formal machinery of BQP synthesizes ideas from quantum mechanics, computability theory, and complexity theory developed over decades. The class's modern formalization is usually credited to Bernstein and Vazirani in the early 1990s, building on Deutsch's foundational notion of a quantum Turing machine and on the broader tradition of bounded-error probabilistic complexity classes pioneered for classical computing by Gill.

Every claim that a quantum computer offers a computational advantage is, formally, a membership claim relative to BQP or a closely related promise-problem class. Shor's factoring algorithm places integer factorization (technically, its decision-problem variant) in BQP, which underlies the security concerns for RSA and other factoring-based public-key cryptosystems discussed in Quantum Algorithms and Cryptanalysis. Quantum simulation algorithms for many-body physics and quantum chemistry — used in materials science and drug discovery research pipelines — are efficient precisely because the relevant simulation tasks lie in BQP, while the same tasks are believed (and in structured cases proven under standard assumptions) to be intractable classically. Cloud quantum computing platforms (superconducting-qubit and trapped-ion systems offered by major quantum computing vendors) implement, in effect, physical realizations of the uniform circuit families that the definition of BQP abstracts over; benchmarking claims like "quantum advantage" or "quantum supremacy" are empirical attempts to exhibit sampling tasks believed to be outside classical BPP but inside a variant of BQP (or the related sampling class BQP-adjacent to it, since raw sampling problems require slightly different formalizations than decision languages). Amplification techniques, identical in spirit to the majority-vote scheme described above, are used in practice to boost the reliability of near-term noisy quantum hardware output before trusting a computed answer, connecting directly to error-mitigation and error-correction strategies built on top of the Quantum Channels and Operations framework. Understanding BQP precisely is also the prerequisite for the open questions that follow — most notably how BQP compares to NP, the subject taken up next in the study of the Quantum Complexity Landscape.

Ask the tutor: How does the relationship between BQP and NP shape what we believe quantum computers can and cannot efficiently solve?