Simple Algorithm
Quantum Computing · Excited State · 24 min

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 2/32/3 is arbitrary.
  • Prove BPP⊆BQP\mathsf{BPP}\subseteq\mathsf{BQP} by simulating coins and reversible logic, and BQP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PSPACE} with a path sum.
  • Explain BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP}, and why an unconditional proof of BPP≠BQP\mathsf{BPP}\neq\mathsf{BQP} 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 L⊆{0,1}∗L\subseteq\{0,1\}^*, where an algorithm must answer "is x∈Lx\in L?". Efficient means a running time polynomial in the input length n=∣x∣n = \abs{x}, 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.

ClassModelAcceptance ruleExample
Pdeterministic, polynomial timealways correctshortest paths; primality (AKS 2002)
BPPrandomized, polynomial timecorrect with probability ≥2/3\ge2/3polynomial identity testing
NPpolynomial-time verifier with a certificateyes: some certificate accepted; no: none isSAT, graph coloring
PPrandomized, polynomial timecorrect with probability >1/2>1/2 (the margin may be exponentially small)MAJ-SAT: do most assignments satisfy a formula?
PSPACEpolynomial memory, any running timealways correctquantified Boolean formulas, generalized games
Known: P⊆BPP⊆PP⊆PSPACE\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE} and P⊆NP⊆PP\mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PP}. Whether any of these inclusions is strict is open, except that P≠EXP\mathsf{P}\neq\mathsf{EXP}.

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 2/32/3 and 1/31/3 can be replaced by any two numbers separated by 1/poly⁡(n)1/\poly(n), thanks to repetition.
DerivationError reduction by majority vote
  1. Pr⁡[run i correct]≥23,Yi:=[run i correct]∈{0,1}  independent\Pr[\text{run } i \text{ correct}]\ge\tfrac23,\qquad Y_i := [\text{run } i \text{ correct}]\in\{0,1\}\ \text{ independent}

    Run the circuit kk times on the same input and output the majority answer.

  2. Pr⁡[majority wrong]≤Pr⁡[1k∑iYi≤12]≤e−2k(2/3−1/2)2=e−k/18\Pr[\text{majority wrong}]\le\Pr\Big[\tfrac1k\textstyle\sum_iY_i\le\tfrac12\Big]\le e^{-2k(2/3-1/2)^2} = e^{-k/18}

    Hoeffding's inequality: the fraction of correct runs must fall 1/61/6 below its mean.

  3. The kk 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.

Predict before you look

Using the bound e−k/18e^{-k/18}, how many runs kk guarantee an error probability of at most 10−610^{-6}?

Show the answer

249 runs

k≥18ln⁡(106)≈248.7k\ge18\ln(10^6)\approx248.7, so 249 runs. Every further 18 runs divide the error bound by ee; doubling kk 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, ∣a,b,0⟩↦∣a,b,ab⟩\ket{a,b,0}\mapsto\ket{a,b,ab}, NOT is XX, and fan-out is a CNOT. Garbage bits are erased by running the circuit backwards (uncomputation).

BPP ⊆ BQP. A fair coin is H∣0⟩H\ket0 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.

DerivationBQP ⊆ PSPACE: summing over paths
  1. ⟨y∣C∣x⟩=⟨y∣GT⋯G1∣x⟩=∑z1,…,zT−1∈{0,1}N ∏t=1T⟨zt∣Gt∣zt−1⟩,z0=x, zT=y\bra{y}C\ket{x} = \bra{y}G_T\cdots G_1\ket{x} = \sum_{z_1,\dots,z_{T-1}\in\{0,1\}^N}\ \prod_{t=1}^{T}\bra{z_t}G_t\ket{z_{t-1}},\qquad z_0 = x,\ z_T = y

    Insert ∑z∣z⟩ ⁣⟨z∣=I\sum_z\dyad{z} = \id between consecutive gates: a Feynman path sum over sequences of basis states (NN is the total number of qubits).

  2. Each factor ⟨zt∣Gt∣zt−1⟩\bra{z_t}G_t\ket{z_{t-1}} is an entry of a 2×22\times2 or 4×44\times4 gate matrix, computable in polynomial time.

  3. Loop over all 2N(T−1)2^{N(T-1)} paths, keeping only the current path and a running sum: exponential time, but only O(NT)\order{NT} bits of memory plus polynomial precision.

  4. Pr⁡[accept]=∑y: y1=1∣⟨y∣C∣x⟩∣2\Pr[\text{accept}] = \sum_{y:\ y_1 = 1}\abs{\bra{y}C\ket{x}}^2

    A second loop over outputs yy, again in polynomial space. Hence BQP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PSPACE} (Bernstein & Vazirani 1997).

A sharper bound: BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP} (Adleman, DeMarrais & Huang 1997). With the gates HH and Toffoli every path contributes ±2−h/2\pm2^{-h/2}, where hh counts the Hadamards, so Pr⁡[1]−Pr⁡[0]\Pr[1]-\Pr[0] equals a difference of two counts of paths divided by 2h2^h. Deciding whether such a difference is positive is exactly what PP machines do. And PP⊆PSPACE\mathsf{PP}\subseteq\mathsf{PSPACE}.

Check your understanding

Suppose someone proves, unconditionally, that BPP≠BQP\mathsf{BPP}\neq\mathsf{BQP}. Which famous open problem would that settle?

  1. P≠NP\mathsf{P}\neq\mathsf{NP}
  2. NP≠coNP\mathsf{NP}\neq\mathsf{coNP}
  3. P≠PSPACE\mathsf{P}\neq\mathsf{PSPACE}
  4. None: it would be a purely quantum statement
Show the answer

C. P≠PSPACE\mathsf{P}\neq\mathsf{PSPACE}

P⊆BPP⊆BQP⊆PSPACE\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PSPACE}. If P=PSPACE\mathsf{P} = \mathsf{PSPACE}, the whole chain collapses and BPP=BQP\mathsf{BPP} = \mathsf{BQP}. So BPP≠BQP\mathsf{BPP}\neq\mathsf{BQP} implies P≠PSPACE\mathsf{P}\neq\mathsf{PSPACE}, 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 NN have a nontrivial factor ≤k\le k?") lies in NP∩coNP\mathsf{NP}\cap\mathsf{coNP} (a factorization certifies both answers) and in BQP by Shor's algorithm. The best known classical algorithm, the number field sieve, takes time exp⁡(O((log⁡N)1/3(log⁡log⁡N)2/3))\exp\big(\order{(\log N)^{1/3}(\log\log N)^{2/3}}\big). 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 Ω(N)\Omega(\sqrt N) queries (Bennett, Bernstein, Brassard & Vazirani 1997), so relative to a random oracle NP⊈BQP\mathsf{NP}\not\subseteq\mathsf{BQP}. In the other direction, Raz and Tal (2018) built an oracle relative to which BQP is not even contained in the polynomial hierarchy PH.

StatementStatus
P⊆BPP⊆BQP⊆PP⊆PSPACE\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}proven
Factoring and discrete logarithms are in BQPproven (Shor 1994)
Factoring is not in BPPconjectured; RSA relies on it
NP⊆BQP\mathsf{NP}\subseteq\mathsf{BQP}believed false; false relative to a random oracle
BQP⊆NP\mathsf{BQP}\subseteq\mathsf{NP}, or BQP⊆PH\mathsf{BQP}\subseteq\mathsf{PH}unknown; false relative to an oracle (Raz–Tal)
BPP≠BQP\mathsf{BPP}\neq\mathsf{BQP}believed; a proof would imply P≠PSPACE\mathsf{P}\neq\mathsf{PSPACE}
Check your understanding

Which statement is an unconditional theorem, not a conjecture or an oracle result?

  1. NP⊈BQP\mathsf{NP}\not\subseteq\mathsf{BQP}
  2. BQP⊈PH\mathsf{BQP}\not\subseteq\mathsf{PH}
  3. Factoring is not in BPP
  4. BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP}
Show the answer

D. BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP}

BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP} 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.
  • P⊆BPP⊆BQP⊆PP⊆PSPACE\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}; path sums simulate quantum circuits in polynomial space.
  • An unconditional proof that BPP≠BQP\mathsf{BPP}\neq\mathsf{BQP} would prove P≠PSPACE\mathsf{P}\neq\mathsf{PSPACE}, 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.

Question 1

Which change to the definition of BQP would change the class (as far as anyone knows)?

  1. Replacing 2/32/3 by 0.9990.999
  2. Replacing the gate set {H,T,CNOT}\{H, T, \mathrm{CNOT}\} by {H,Toffoli}\{H, \mathrm{Toffoli}\}
  3. Allowing intermediate measurements and classical control
  4. Requiring only acceptance probability >1/2>1/2 for yes-instances and ≤1/2\le1/2 for no-instances
Show the answer

D. Requiring only acceptance probability >1/2>1/2 for yes-instances and ≤1/2\le1/2 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.

Question 2

The path-sum simulation proves BQP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PSPACE}. Which resource does it use exponentially much of?

  1. Time
  2. Memory
  3. Both time and memory
  4. Neither
Show the answer

A. Time

It visits exponentially many paths one at a time, reusing the same polynomial-size memory for each.

Question 3

Factoring is in BQP and in NP∩coNP\mathsf{NP}\cap\mathsf{coNP}. Why is this not evidence that NP⊆BQP\mathsf{NP}\subseteq\mathsf{BQP}?

  1. Shor's algorithm is probabilistic
  2. Factoring is known to be in P
  3. Factoring is not believed NP-complete: if it were, NP would equal coNP
  4. 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 NP∩coNP\mathsf{NP}\cap\mathsf{coNP} is NP-hard only if NP=coNP\mathsf{NP} = \mathsf{coNP}.

Question 4

What does the Raz–Tal oracle separation establish?

  1. BQP⊈PH\mathsf{BQP}\not\subseteq\mathsf{PH} unconditionally
  2. There is an oracle relative to which BQP⊈PH\mathsf{BQP}\not\subseteq\mathsf{PH}, so no relativizing proof can show BQP⊆PH\mathsf{BQP}\subseteq\mathsf{PH}
  3. NP⊆BQP\mathsf{NP}\subseteq\mathsf{BQP} relative to a random oracle
  4. P≠BQP\mathsf{P}\neq\mathsf{BQP}
Show the answer

B. There is an oracle relative to which BQP⊈PH\mathsf{BQP}\not\subseteq\mathsf{PH}, so no relativizing proof can show BQP⊆PH\mathsf{BQP}\subseteq\mathsf{PH}

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.

Question 5

A quantum algorithm answers a decision problem correctly with probability 0.510.51 on every input. Is the problem in BQP?

  1. No: BQP requires correctness probability at least 2/32/3
  2. Only if the probability is exactly 0.510.51
  3. Yes: a constant gap above 1/21/2 can be amplified by majority vote with constant overhead
  4. No: such an algorithm defines PP
Show the answer

C. Yes: a constant gap above 1/21/2 can be amplified by majority vote with constant overhead

By Hoeffding, O(log⁡(1/δ)/0.012)\order{\log(1/\delta)/0.01^2} repetitions push the error below δ\delta. Any gap of at least 1/poly⁡(n)1/\poly(n) suffices.

Go deeper

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.