BQP, BPP, QMA, and their relationships
Which problems can a quantum computer solve efficiently, and how does that set relate to what ordinary computers, or computers with lucky guesses, can do? Complexity theory sorts problems into classes and asks which classes contain which. For quantum computers, two containments are proven: quantum computers can do everything randomized classical computers can, and they can be simulated with polynomial memory. Almost everything in between is open.
On the plate: a map of the classes. Choose a relation to see whether it is proven, known only relative to an oracle, or conjectured.
BQP
A decision problem is in BQP (bounded-error quantum polynomial time) if a uniform family of polynomial-size circuits, one per input length and generated by a classical program, answers correctly with probability at least 2/3 on every input. Uniformity matters: without it, a circuit family could hide the answer to an undecidable problem in its design. The constant 2/3 is arbitrary; repeating and taking the majority drives the error down exponentially. Ethan Bernstein and Umesh Vazirani defined the class in 1993 (journal version 1997). Its classical counterparts are P (deterministic) and BPP (randomized, bounded error). Established
The map
Select a relation: , , , , , .
BPP ⊆ BQP holds because a quantum computer can flip coins. BQP ⊆ PP ⊆ PSPACE was proved by Leonard Adleman, Jonathan DeMarrais and Ming-Deh Huang in 1997. Whether BQP contains NP is unknown; most researchers believe it does not, because Grover’s quadratic speedup is optimal for unstructured search (Chapter 130). In 2018 Ran Raz and Avishay Tal constructed an oracle relative to which BQP is not contained in the polynomial hierarchy PH, the tower of classes built over NP: in that oracle world, quantum computers solve problems beyond any finite tower of guesses and checks. Factoring is in BQP by Shor, but is believed to be neither in P nor NP-complete. Established for the proven relations; Debated for the conjectures.
Why BQP ⊆ PSPACE: sum over paths
An output amplitude is a sum over all paths through the circuit, like Feynman’s path integral (Chapter 53). With = 10 Hadamard gates, there are paths, each contributing . A classical computer can add them one at a time, reusing the same memory: exponential time, but only polynomial space. Counting positive versus negative paths is exactly what PP machines do, which gives BQP ⊆ PP.
QMA is the quantum analogue of NP: a quantum verifier checks a quantum proof (a “witness” state). QCMA allows only classical proofs. Whether QMA = QCMA is open; Scott Aaronson and Greg Kuperberg separated them relative to a quantum oracle in 2007, and separations relative to classical oracles are still only partial. Chapter 129 shows the local Hamiltonian problem is complete for QMA.
What you now have
A rigorous definition of BQP with uniformity, the proven inclusions BPP ⊆ BQP ⊆ PP ⊆ PSPACE, the sum-over-paths argument, QMA and QCMA, the Raz–Tal oracle, and the open questions.
· · ·
Three questions to carry with you.
And one to work out. A circuit has 20 Hadamard gates. How many paths does the sum over paths contain?
Sources: E. Bernstein and U. Vazirani, SIAM J. Comput. 26, 1411 (1997). L. M. Adleman, J. DeMarrais and M.-D. A. Huang, SIAM J. Comput. 26, 1524 (1997). J. Watrous, “Quantum computational complexity”, arXiv:0804.3401 (2008). R. Raz and A. Tal, Proc. 51st ACM STOC (2019). S. Aaronson and G. Kuperberg, Theory Comput. 3, 129 (2007). A. Kitaev, A. Shen and M. Vyalyi, Classical and Quantum Computation (AMS, 2002).