BQP

BQP (Bounded-error Quantum Polynomial time) is the complexity class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. The "bounded-error" requirement means the quantum algorithm must be correct with probability ≥ 2/3; this bound can be amplified to exponentially small error by repetition, so the 1/3 threshold is not arbitrary but marks the point where efficient amplification becomes possible.

BQP sits at the intersection of three domains: quantum physics, computational complexity, and the theory of efficient computation. Understanding its boundaries, its relationships to classical classes, and its physical interpretation is essential for grasping what quantum computers can and cannot do.

The Definition and What It Captures

A problem is in BQP if there exists a quantum circuit of polynomial size that, given any input of length n, outputs the correct answer with probability at least 2/3. The quantum circuit may use superposition, entanglement, and interference — the three resources that distinguish quantum from classical computation — but its runtime must scale polynomially in the input length.

The polynomial bound on circuit size is the "P" in BQP. The bounded error is the "B." The quantum substrate is implicit in the model: BQP is defined with respect to the quantum circuit model, not the Turing machine, because quantum computation is not merely a faster classical computation but a different computational model whose state space is exponentially larger than its classical counterpart.

What We Know: Containments

The known containments form a chain:

P ⊆ BPP ⊆ BQP ⊆ PSPACE

P ⊆ BQP is immediate: a classical polynomial-time algorithm is a special case of a quantum polynomial-time algorithm that happens not to use superposition or entanglement.

BPP ⊆ BQP follows because a quantum computer can simulate a classical randomized algorithm by preparing superpositions and measuring. The containment is believed to be strict — Shor's algorithm for integer factoring provides strong evidence, since factoring is believed to lie outside BPP (and indeed outside P), yet is in BQP.

BQP ⊆ PSPACE was proven by Bernstein and Vazirani (1993) and independently by Adleman, Demarrais, and Huang (1997). The proof shows that a quantum computation can be simulated by a classical algorithm using polynomial space, even though the naive simulation requires exponential time. This containment is also believed to be strict: it would imply P = PSPACE if BQP = PSPACE, which is considered extraordinarily unlikely.

The relationship between BQP and NP is the central open problem. It is not known whether NP ⊆ BQP (whether quantum computers can efficiently solve all NP problems) or whether BQP ⊆ NP (whether quantum solutions can be efficiently verified classically). Most complexity theorists suspect that NP is not contained in BQP — that quantum computers do not solve NP-complete problems in polynomial time — but this remains unproven. The suspicion is grounded in oracle results: relative to a random oracle, BQP does not contain NP. But oracle results do not translate to unconditional proofs, and the possibility remains open.

The Flagship Problems: Factoring and Simulation

Two problems define BQP's significance:

Integer factoring (and the related discrete logarithm problem) is in BQP via Shor's algorithm (1994). The algorithm uses the quantum Fourier transform to extract the period of a function, from which factors can be recovered. The consequence for cryptography is direct: RSA, Diffie-Hellman, and elliptic-curve cryptosystems depend on the presumed hardness of factoring and discrete log for classical computers. A scalable quantum computer would break these systems.

Quantum simulation — the simulation of quantum mechanical systems — is the other flagship application. Feynman (1982) observed that simulating quantum systems on classical computers requires exponential resources in general, while a quantum computer naturally operates on the same state space as the system being simulated. Quantum simulation is in BQP because the dynamics of a finite quantum system can be approximated by a polynomial-size quantum circuit (via Trotter-Suzuki decomposition or other Hamiltonian simulation techniques). The applications span materials science, drug discovery, and fundamental physics.

The Physical Interpretation: BQP as a Claim About Nature

BQP is not merely a mathematical object. It is a claim about what nature permits at the level of information processing. The class BQP is defined with respect to the standard quantum circuit model, which abstracts away from physical implementation. But the abstraction is anchored in the physical theory of quantum mechanics. If quantum mechanics is correct as a description of physical reality, then BQP is the class of problems efficiently solvable by a physical device operating according to quantum mechanical principles.

This physical grounding distinguishes BQP from classes like NP or PSPACE, which are defined without reference to any physical theory. Whether P = NP is a mathematical question. Whether BQP contains problems outside BPP is a physical question: it asks whether there exist physical processes — quantum interference, entanglement — that permit efficient computation beyond what classical randomness achieves.

The physical interpretation also carries a warning: BQP assumes a fully coherent quantum computer. Real quantum devices operate at finite temperature, with finite coherence times, and with gate errors. The threshold theorem of quantum fault tolerance (Aharonov, Ben-Or; Kitaev) shows that if the physical error rate per gate is below a threshold, logical qubits can be protected indefinitely. But the threshold is a physical claim: it requires that the universe permits noise levels below the threshold and that engineering can achieve them. Whether this is true at the scale required for cryptographically relevant factoring remains open.

BQP and the Landscape of Complexity

Beyond the standard containments, BQP relates to other quantum classes in ways that illuminate the structure of quantum computation:

• PostBQP (BQP with postselection) equals PP (Probabilistic Polynomial time), a surprising result due to Aaronson (2005). This shows that the gap between BQP and classical probabilistic classes narrows dramatically if one permits the unrealistic power of postselection.
• QMA (Quantum Merlin-Arthur) is the quantum analogue of NP. Where NP asks whether a classical witness can be verified in polynomial time, QMA asks whether a quantum witness (a quantum state) can be verified by a quantum computer. QMA contains BQP and is believed to be strictly larger.
• BQP^BQP (BQP with a BQP oracle) equals BQP. This self-lowness is analogous to the classical result that P^P = P, and reflects the closure of efficient quantum computation under composition.

The Limits of Quantum Advantage

BQP is large enough to contain problems of enormous practical consequence (factoring, quantum simulation) and small enough that it almost certainly does not contain NP-complete problems. This intermediate status — larger than BPP, smaller than PSPACE, incomparable with NP — is what makes BQP scientifically interesting. It marks a boundary between what classical randomness achieves and what quantum physics permits.

The honest assessment is that the boundaries of BQP are less well understood than the boundaries of P or NP. We do not know whether BQP contains all of NP. We do not know whether BQP is contained in the polynomial hierarchy. We do not know whether there exist problems in BQP that are not in BPP. The quantum speedup for factoring is proven; the quantum speedup for generic search (Grover's algorithm) is only quadratic; and for most problems, no quantum speedup is known at all.

BQP is not a theory of everything computable. It is a theory of what becomes efficiently computable when one gains access to quantum interference. That gain is substantial for specific problems and apparently negligible for most. The class is therefore not merely a mathematical curiosity. It is a map of the territory where quantum mechanics changes what can be efficiently computed — and that territory, while smaller than early quantum computing enthusiasts hoped, is large enough to transform cryptography, materials science, and our understanding of physical computation.