Select a Class
Containment Relations
Click a node to highlight its containment chains. Click the cards below for details.
Click a node to highlight containment paths. Click the background to reset.
The Classical Backbone
P ⊆ BPP ⊆ PSPACE ⊆ EXP ✓ provenEvery polynomial-time deterministic algorithm is also a randomized one (P ⊆ BPP). BPP can be simulated in polynomial space, and PSPACE in exponential time. These inclusions are unconditional. The time hierarchy theorem gives us the only unconditional strict separation: P ≠ EXP.
Examples: Sorting ∈ P • Polynomial Identity Testing ∈ BPP • TQBF ∈ PSPACE-complete
Quantum in the Landscape
P ⊆ BPP ⊆ BQP ⊆ PSPACE ✓ provenQuantum computers can simulate classical probabilistic machines (BPP ⊆ BQP). Conversely, any quantum computation can be simulated in polynomial space by tracking amplitudes path by path — giving BQP ⊆ PSPACE. Whether any of these inclusions are strict remains one of the central open questions.
Examples: Dijkstra’s algorithm ∈ P • Miller-Rabin primality ∈ BPP • Factoring ∈ BQP
Verification Power
BQP ⊆ QMA ⊆ PSPACE ✓?BQP problems need no witness, so they're trivially in QMA. QMA sits inside PSPACE because a PSPACE machine can iterate over all possible quantum witnesses and simulate the verifier. Whether BQP = QMA or QMA = PSPACE remains unknown.
Examples: Factoring ∈ BQP • Local Hamiltonian ∈ QMA-complete • TQBF ∈ PSPACE-complete
QMA vs NP
NP ⊆ QMA ✓?A classical proof is a special case of a quantum proof — the QMA verifier can read classical bits. Whether this inclusion is strict (i.e., whether quantum proofs are more powerful than classical ones) remains an important open question.
Examples: SAT ∈ NP-complete • Local Hamiltonian ∈ QMA-complete
BQP vs BPP — The Quantum Advantage?
BPP ⊆ BQP (strict?) ? openWe believe quantum computers can solve problems that classical randomized algorithms cannot (e.g., factoring via Shor's algorithm). Proving BPP ≠ BQP would confirm quantum computational advantage unconditionally. This is arguably the most important open question in quantum complexity theory.
Examples: Factoring ∈ BQP ∩ NP • Miller-Rabin primality ∈ BPP
P vs BPP — Derandomization
P ⊆ BPP (P = BPP?) ✓? conj.It is widely conjectured that P = BPP — randomness can be removed from any efficient algorithm (derandomization). This would mean BPP ⊆ NP, since P ⊆ NP is trivially true. The best evidence comes from the Impagliazzo–Wigderson theorem: if any problem in E = DTIME($2^{O(n)}$) requires exponential-size circuits, then P = BPP. This is believed to hold, making the conjecture strongly supported.
Key result: Sipser–Lautemann theorem: BPP ⊆ Σ2 ∩ Π2 (second level of the polynomial hierarchy)
BQP vs NP — Orthogonal Power?
BQP ⊄ NP? NP ⊄ BQP? ? openBQP and NP are believed to be incomparable. Quantum computers can solve some problems outside NP (like certain sampling problems with no short classical certificate), and NP contains problems (like NP-complete ones) believed to be outside BQP. Oracle separations support both directions.
Examples: Factoring ∈ BQP ∩ NP • SAT ∈ NP-complete (probably ∉ BQP) • Forrelation ∈ BQP (probably ∉ NP)
BQP vs PSPACE — Limits of Quantum
BQP ⊆ PSPACE (strict?) ✓?A classical machine with polynomial space can simulate any quantum circuit by computing amplitudes via the Feynman path-sum method: enumerate all $2^n$ computational paths one at a time, each requiring only polynomial space. The space is reused between paths. Whether quantum computers are strictly weaker than PSPACE remains open, but most researchers believe BQP ≠ PSPACE.
Key insight: Space is reusable but time is not — this is why PSPACE can simulate quantum computation despite the exponential state space.
What if P = NP?
Cryptography as we know it would collapse. Every NP problem (including SAT, graph coloring, scheduling) would have efficient solutions. Mathematical proof search would become tractable. However, it would not directly affect quantum classes — BQP's relationship to NP would remain unclear.
What if BQP = BPP?
Quantum computers would offer no super-polynomial speedup over classical probabilistic computation. Shor's algorithm would imply classical polynomial-time factoring. Billions invested in quantum hardware would be "only" for constant-factor improvements. Most researchers believe this is false.
What if BQP ⊇ NP?
Quantum computers could solve NP-complete problems efficiently. This would be revolutionary but is considered very unlikely — there's strong oracle evidence against it. It would imply quantum computers can solve problems like 3-SAT and the traveling salesman problem in polynomial time.
What if P ≠ BPP?
Randomness would be a genuinely useful computational resource — there would exist problems solvable efficiently with coin flips but not deterministically. This would contradict the prevailing conjecture and imply that no problem in E = DTIME($2^{O(n)}$) requires exponential-size circuits, undermining longstanding beliefs in circuit complexity.
What if QMA = NP?
Quantum proofs would be no more powerful than classical proofs. The Local Hamiltonian Problem would reduce to SAT. Ground-state energy estimation could be verified with a classical certificate. This would imply quantum entanglement in witnesses is computationally useless, which is considered unlikely given the structure of quantum mechanics.
What if PSPACE = P?
All of NP, BQP, QMA, and PSPACE would collapse into P. Every game, every quantified formula, every quantum computation would be efficiently solvable deterministically. This is considered extremely unlikely.
BQP Simulator
Explore the key idea behind BQP: a quantum algorithm produces the correct answer with probability $\ge 2/3$. Run a simulated quantum algorithm and observe how repeating the computation amplifies success probability via majority vote.
Bounded-Error Amplification
A BQP algorithm answers correctly with probability $\ge 2/3$. By running it $k$ times and taking a majority vote, the error probability drops exponentially: $\varepsilon \le e^{-\Omega(k)}$.
Individual Run Results
Cumulative Success Rate (convergence to $p$)
Error Probability Decay (log scale)
Why This Matters
The amplification lemma is what makes BQP robust: the exact threshold ($2/3$) doesn't matter. Any constant probability strictly above $1/2$ can be boosted to $1 - 2^{-n}$ with only a polynomial number of repetitions. By the Chernoff bound, $k = O(\log(1/\delta))$ repetitions suffice to achieve error $\delta$. This is why BQP is defined with bounded error — the "B" in BQP.
Test Your Knowledge
Answer these questions to check your understanding. Use hints if needed (costs 0.5 points).
Major Open Problems
Some of the deepest unsolved questions in quantum complexity theory. Click to expand the deep dive.
Glossary & Reference
Searchable reference of key terms in quantum complexity theory.