Quantum Complexity: BQP & Beyond
What quantum computers can efficiently solve, formally.
"Quantum computers are faster" is not a theorem. To say precisely what they can do efficiently you need complexity classes. BQP captures efficient quantum computation, and what we know about it is a mix of solid theorems, oracle evidence and famous open problems.
What you’ll learn
- Define BQP through uniform families of polynomial-size quantum circuits with bounded error, and explain why the constant is arbitrary.
- Prove by simulating coins and reversible logic, and with a path sum.
- Explain , and why an unconditional proof of would separate P from PSPACE.
- Place factoring and NP-complete problems relative to BQP, separating theorems from conjectures and oracle results.
- Preview QMA (quantum proofs) and sampling-based evidence for quantum advantage.
Problems, resources, classes
Complexity theory studies decision problems: languages , where an algorithm must answer "is ?". Efficient means a running time polynomial in the input length , in the worst case over inputs. Polynomials are closed under composition (an efficient algorithm calling an efficient subroutine stays efficient), which makes the classes robust to the details of the machine model.
| Class | Model | Acceptance rule | Example |
|---|---|---|---|
| P | deterministic, polynomial time | always correct | shortest paths; primality (AKS 2002) |
| BPP | randomized, polynomial time | correct with probability | polynomial identity testing |
| NP | polynomial-time verifier with a certificate | yes: some certificate accepted; no: none is | SAT, graph coloring |
| PP | randomized, polynomial time | correct with probability (the margin may be exponentially small) | MAJ-SAT: do most assignments satisfy a formula? |
| PSPACE | polynomial memory, any running time | always correct | quantified Boolean formulas, generalized games |
Defining BQP
Three choices in this definition do not matter, and one does:
- Uniformity (circuits produced by an efficient algorithm) is essential: otherwise one could hard-wire the answers to an uncomputable problem into the circuit family.
- The gate set is irrelevant: by the Solovay–Kitaev theorem, any universal set approximates any other with polylogarithmic overhead.
- The constants and can be replaced by any two numbers separated by , thanks to repetition.
Run the circuit times on the same input and output the majority answer.
Hoeffding's inequality: the fraction of correct runs must fall below its mean.
The runs and the majority vote fit into one circuit (measure at the end, by deferred measurement), so the amplified algorithm is again a BQP circuit, polynomially larger, with exponentially small error.
Using the bound , how many runs guarantee an error probability of at most ?
Show the answer
249 runs
, so 249 runs. Every further 18 runs divide the error bound by ; doubling squares it.
Quantum computers can do everything classical ones can
P ⊆ BQP. Any classical circuit can be made reversible: a Toffoli gate computes AND into a fresh ancilla, , NOT is , and fan-out is a CNOT. Garbage bits are erased by running the circuit backwards (uncomputation).
BPP ⊆ BQP. A fair coin is measured. By deferred measurement the coins can stay quantum until the end, so a randomized algorithm becomes a quantum circuit with the same acceptance probabilities.
Upper bounds: BQP ⊆ PP ⊆ PSPACE
A classical computer can obviously simulate a quantum circuit in exponential time. Remarkably, it needs only polynomial memory.
Insert between consecutive gates: a Feynman path sum over sequences of basis states ( is the total number of qubits).
Each factor is an entry of a or gate matrix, computable in polynomial time.
Loop over all paths, keeping only the current path and a running sum: exponential time, but only bits of memory plus polynomial precision.
A second loop over outputs , again in polynomial space. Hence (Bernstein & Vazirani 1997).
A sharper bound: (Adleman, DeMarrais & Huang 1997). With the gates and Toffoli every path contributes , where counts the Hadamards, so equals a difference of two counts of paths divided by . Deciding whether such a difference is positive is exactly what PP machines do. And .
Suppose someone proves, unconditionally, that . Which famous open problem would that settle?
- None: it would be a purely quantum statement
Show the answer
C.
. If , the whole chain collapses and . So implies , and proving quantum speedups unconditionally is at least as hard as that. This is why all evidence for quantum advantage is conditional or relativized.
Factoring, NP, and the limits of speedup
The decision version of factoring ("does have a nontrivial factor ?") lies in (a factorization certifies both answers) and in BQP by Shor's algorithm. The best known classical algorithm, the number field sieve, takes time . Factoring is not believed to be NP-complete: if it were, NP would equal coNP. So factoring is evidence that BQP is larger than BPP, but only conditional evidence.
For NP-complete problems no polynomial-time quantum algorithm is known. Grover's algorithm speeds up brute-force search quadratically, and that is optimal: unstructured search needs queries (Bennett, Bernstein, Brassard & Vazirani 1997), so relative to a random oracle . In the other direction, Raz and Tal (2018) built an oracle relative to which BQP is not even contained in the polynomial hierarchy PH.
| Statement | Status |
|---|---|
| proven | |
| Factoring and discrete logarithms are in BQP | proven (Shor 1994) |
| Factoring is not in BPP | conjectured; RSA relies on it |
| believed false; false relative to a random oracle | |
| , or | unknown; false relative to an oracle (Raz–Tal) |
| believed; a proof would imply |
Which statement is an unconditional theorem, not a conjecture or an oracle result?
- Factoring is not in BPP
Show the answer
D.
is proved by the path-sum argument (Adleman, DeMarrais & Huang 1997). The other three are believed, or proven only relative to oracles.
Beyond BQP: quantum proofs and sampling
QMA is the quantum analogue of NP: a "yes" answer comes with a quantum state as proof, checked by a BQP verifier. Kitaev proved that estimating the ground-state energy of a local Hamiltonian is QMA-complete, so finding ground states is hard in the worst case even for quantum computers.
Sampling problems ask for samples from a distribution rather than a yes/no answer. If certain quantum output distributions (BosonSampling, IQP circuits, random circuits) could be sampled classically to small multiplicative error, the polynomial hierarchy would collapse (Bremner, Jozsa & Shepherd 2011; Aaronson & Arkhipov 2011). This is the theory behind quantum-advantage experiments such as Google's 2019 53-qubit Sycamore demonstration.
Key takeaways
- BQP = problems solved by uniform polynomial-size quantum circuits with bounded error; it is robust to the gate set, the error constants and intermediate measurements.
- ; path sums simulate quantum circuits in polynomial space.
- An unconditional proof that would prove , so evidence for quantum advantage is conditional (factoring) or relativized (oracles).
- Factoring is in BQP; NP-complete problems are believed to lie outside it, and Grover's quadratic speedup is optimal for unstructured search.
- QMA (quantum proofs) and sampling problems extend the picture, each with its own deep dive.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which change to the definition of BQP would change the class (as far as anyone knows)?
- Replacing by
- Replacing the gate set by
- Allowing intermediate measurements and classical control
- Requiring only acceptance probability for yes-instances and for no-instances
Show the answer
D. Requiring only acceptance probability for yes-instances and for no-instances
With an unbounded (possibly exponentially small) gap the class becomes PP, which contains NP. The other changes are harmless: amplification, universality of gate sets, and deferred measurement.
The path-sum simulation proves . Which resource does it use exponentially much of?
- Time
- Memory
- Both time and memory
- Neither
Show the answer
A. Time
It visits exponentially many paths one at a time, reusing the same polynomial-size memory for each.
Factoring is in BQP and in . Why is this not evidence that ?
- Shor's algorithm is probabilistic
- Factoring is known to be in P
- Factoring is not believed NP-complete: if it were, NP would equal coNP
- Factoring is easy for most inputs
Show the answer
C. Factoring is not believed NP-complete: if it were, NP would equal coNP
An efficient algorithm for one problem in NP says nothing about all of NP unless that problem is NP-hard, and a problem in is NP-hard only if .
What does the Raz–Tal oracle separation establish?
- unconditionally
- There is an oracle relative to which , so no relativizing proof can show
- relative to a random oracle
Show the answer
B. There is an oracle relative to which , so no relativizing proof can show
Oracle results show what proof techniques that treat subroutines as black boxes cannot do. Raz and Tal found a black-box problem (a Forrelation variant) that quantum computers solve with few queries but no PH machine can.
A quantum algorithm answers a decision problem correctly with probability on every input. Is the problem in BQP?
- No: BQP requires correctness probability at least
- Only if the probability is exactly
- Yes: a constant gap above can be amplified by majority vote with constant overhead
- No: such an algorithm defines PP
Show the answer
C. Yes: a constant gap above can be amplified by majority vote with constant overhead
By Hoeffding, repetitions push the error below . Any gap of at least suffices.
Go deeper
- BQP: Definition & Containments · BPP ⊆ BQP ⊆ PP ⊆ PSPACE, and what we do not know.
- QMA & the Local Hamiltonian Problem · The quantum Cook–Levin theorem.
- Sampling Advantage & Complexity Evidence · Why sampling problems give the strongest evidence for advantage.
Further reading
- E. Bernstein & U. Vazirani, "Quantum complexity theory", SIAM Journal on Computing 26, 1411 (1997).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, Chs. 3–4 (Cambridge, 10th anniv. ed., 2010).
- S. Aaronson, Quantum Computing Since Democritus (Cambridge, 2013).
- J. Watrous, "Quantum computational complexity", in Encyclopedia of Complexity and Systems Science (Springer, 2009); arXiv:0804.3401.