Projects / An evolving atlas

Quantum
Complexity Zoo

Pull a membrane.
Follow an idea through time.

DRAG A BOUNDARY · SCROLL TO ZOOM

Inclusion · equality unresolved in this atlas Proven strict inclusion Unresolved / oracle-only comparison Example problem

Nested membranes show recorded inclusions. Space between membranes does not establish a separation. Select two classes to read the exact relation; incidental overlaps and example positions make no additional claims.

A HISTORY IN PAPERS

1937196519932021

Jump to a paper milestone

In the atlas

Example problems at this date

Memberships are limited to this timeline. An unlisted membership is unknown to this dataset, not a nonmembership result. Promise problems are listed separately and are not drawn as languages.

How to read this atlas & its dates

The membranes compare language classes with standard uniform computation and bounded error where applicable. Promise problems are identified separately and are not plotted as languages.

Dates use the cited conference or journal publication (including original online publication), not later digitization or preprint dates. A preprint-only source is explicitly marked. Definition events mark a documented milestone in this curated tour, not a claim of priority for the name. Some links point to expanded versions; those are labeled.

Thin, flexible boundaries represent inclusions whose strictness is not established here. Thick, firmer boundaries indicate a recorded strict relation. Select a class to make material and line styles relative to that class. Equal classes share a membrane and retain all their names. Oracle separations are annotations, never unconditional splits.

This is a curated set of milestones, not an exhaustive literature survey. “Unresolved in this atlas” also includes missing evidence. Definitions use modern notation. Timeline steps are evenly spaced by event, not by elapsed years.

This interactive atlas needs JavaScript. The cited milestones are listed below.

1937 — Computable languages (R). A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem.

1937 — Recognizable languages (RE). A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem.

1937 — HALT ∈ RE. A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem.

1937 — R ⊊ RE. A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem.

1937 — HALT ∉ R. A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem.

1965-05 — Time complexity classes (EXP). J. Hartmanis, R. E. Stearns. On the computational complexity of algorithms.

1965-06 — Polynomial time as "efficient" (P). A. Cobham; J. Edmonds. The intrinsic computational difficulty of functions; Paths, trees, and flowers.

1965-06 — P ⊊ EXP. J. Hartmanis, R. E. Stearns. On the computational complexity of algorithms.

1965-10 — Space-bounded computation (PSPACE). P. M. Lewis II, R. E. Stearns, J. Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages.

1971-05 — NP and NP-completeness. S. A. Cook. The complexity of theorem-proving procedures.

1971-05 — SAT ∈ NP (NP-complete). S. A. Cook. The complexity of theorem-proving procedures.

1971-05 — FACTORING ∈ NP. S. A. Cook. The complexity of theorem-proving procedures.

1971-05 — GI ∈ NP. S. A. Cook. The complexity of theorem-proving procedures.

1972-05 — Nondeterministic time hierarchy (NEXP). S. A. Cook. A hierarchy for nondeterministic time complexity.

1972-05 — NEXP ⊊ R. J. Hartmanis, R. E. Stearns. On the computational complexity of algorithms.

1972-10 — The polynomial hierarchy (PH). A. R. Meyer, L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space.

1973-04 — TQBF ∈ PSPACE (PSPACE-complete). L. J. Stockmeyer, A. R. Meyer. Word problems requiring exponential time: preliminary report.

1975-09 — PRIMES ∈ NP. V. R. Pratt. Every prime has a succinct certificate.

1977-12 — Probabilistic Turing machines (PP). J. Gill. Computational complexity of probabilistic Turing machines.

1977-12 — Bounded-error randomness (BPP). J. Gill. Computational complexity of probabilistic Turing machines.

1977-12 — MAJSAT ∈ PP (PP-complete). J. Gill. Computational complexity of probabilistic Turing machines.

1977-12 — PRIMES ∈ BPP. R. Solovay, V. Strassen. A fast Monte-Carlo test for primality.

1978-01 — NP ⊊ NEXP. J. I. Seiferas, M. J. Fischer, A. R. Meyer. Separating nondeterministic time complexity classes.

1983-11 — BPP ⊆ PH. C. Lautemann. BPP and the polynomial hierarchy.

1985-05 — Arthur–Merlin games (AM). L. Babai. Trading group theory for randomness.

1985-05 — Merlin–Arthur games (MA). L. Babai. Trading group theory for randomness.

1985-05 — Interactive proof systems (IP). S. Goldwasser, S. Micali, C. Rackoff. The knowledge complexity of interactive proof systems.

1988-05 — Multi-prover interactive proofs (MIP). M. Ben-Or, S. Goldwasser, J. Kilian, A. Wigderson. Multi-prover interactive proofs: how to remove intractability assumptions.

1990-10 — PH ⊆ IP. C. Lund, L. Fortnow, H. Karloff, N. Nisan. Algebraic methods for interactive proof systems.

1990-10 — PP ⊆ IP. C. Lund, L. Fortnow, H. Karloff, N. Nisan. Algebraic methods for interactive proof systems.

1990-10 — IP = PSPACE. A. Shamir. IP = PSPACE.

1990-10 — MIP = NEXP. L. Babai, L. Fortnow, C. Lund. Non-deterministic exponential time has two-prover interactive protocols.

1993-05 — Quantum complexity theory (BQP). E. Bernstein, U. Vazirani. Quantum complexity theory.

1994-11 — BQP ⊄ BPP relative to an oracle. D. R. Simon. On the power of quantum computation.

1994-11 — FACTORING ∈ BQP. P. W. Shor. Algorithms for quantum computation, discrete logarithms and factoring.

1997-10 — BQP ⊆ PP. L. M. Adleman, J. DeMarrais, M.-D. A. Huang. Quantum computability.

1999-10 — Quantum interactive proofs (QIP). J. Watrous. PSPACE has constant-round quantum interactive proof systems.

2000-05 — Quantum Merlin–Arthur (QMA). A. Kitaev, J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.

2000-05 — QIP ⊆ EXP. A. Kitaev, J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.

2000-05 — QMA ⊆ PP. A. Kitaev, J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.

2002 — k-LOCAL HAMILTONIAN ∈ QMA (QMA-complete). A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi. Classical and Quantum Computation.

2002-10 — Classical proofs, quantum verifier (QCMA). D. Aharonov, T. Naveh. Quantum NP — a survey.

2003-12 — Multiple unentangled Merlins (QMA(2)). H. Kobayashi, K. Matsumoto, T. Yamakami. Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?.

2004-06 — Entangled provers (MIP*). R. Cleve, P. Høyer, B. Toner, J. Watrous. Consequences and limits of nonlocal strategies.

2004-09 — PRIMES ∈ P. M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P.

2005-09 — Postselected quantum computing (PostBQP). S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time.

2005-09 — PostBQP = PP. S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time.

2010-06 — QIP = PSPACE. R. Jain, Z. Ji, S. Upadhyay, J. Watrous. QIP = PSPACE.

2012-10 — NEXP ⊆ MIP*. T. Ito, T. Vidick. A multi-prover interactive proof for NEXP sound against entangled provers.

2019-06 — BQP ⊄ PH relative to an oracle. R. Raz, A. Tal. Oracle separation of BQP and PH.

2021-11 — MIP* = RE. Z. Ji, A. Natarajan, T. Vidick, J. Wright, H. Yuen. MIP* = RE.