Quantum Complexity Theory

This document collects the basic definitions of quantum complexity theory: models of quantum computation (quantum Turing machines, uniform circuit families, query model), the standard quantum complexity classes ($\mathsf{BQP}$, $\mathsf{EQP}$, $\mathsf{QMA}$, $\mathsf{QIP}$, …), gate-set considerations and Solovay–Kitaev, the standard inclusions and separations, oracle results, and the major open problems. It is intended as a reference companion to math/complexity-theory.md (classical complexity) and to misc/deutsch-jozsa.md (a worked algorithm in the query model).

For broader quantum-computing background and hands-on code see the qcfront project. For the concrete algorithm-engineering side — how classical predicates compile into the quantum oracles and circuits that the cost models below count gates and queries against — see misc/quantum-algorithms.md.

1. Why a Separate Model?

Classical complexity (math/complexity-theory.md § 1) measures resources on a Turing machine — discrete state transitions on a tape, deterministic or nondeterministic. Quantum computation requires unitary evolution on a Hilbert space, with measurement at the end producing a classical outcome distributed by the Born rule. This is not a Turing machine in the usual sense; even the "quantum Turing machine" (below) is rarely the working model in practice.

The standard cost measures are:

• Quantum time = number of elementary unitary gates applied (or circuit depth = longest input-to-output gate path).
• Quantum space = number of qubits used.
• Query complexity = number of uses of an oracle unitary $U_f$ (an oracle for a classical function, treated as cost 1).

The relationship between these mirrors the classical case but with quantum-specific subtleties (no-cloning forbids free copying; measurement is irreversible; gate sets are finite but only approximate arbitrary unitaries).

2. Models of Quantum Computation

2.1 Quantum circuits

A quantum circuit on $n$ qubits is a sequence $U=U_T{U}_{T-1}\cdots U_1$ of gates, each $U_t$ a unitary acting on a constant number of qubits (typically 1 or 2). The Hilbert space is $\mathcal{H}=({\mathbb{C}}^2{)}^{\otimes n}$ of dimension $2^n$.

Inputs are encoded as basis states $|x⟩=|x_1{x}_2\cdots x_n⟩$ for $x\in \{0,1{\}}^n$; the output is read off by measuring a designated subset of qubits in the computational basis. By the Born rule, outcome $y$ occurs with probability $|⟨y|U|x⟩{|}^2$.

A circuit family is a sequence $\{C_n{\}}_{n\in \mathbb{N}}$ with $C_n$ acting on (a polynomial in $n$) qubits, deciding a language $L$ via "$x\in L⟺$ majority outcome of $C_{|x|}(x)$ is $1$" (with whatever error model the class allows).

2.2 Uniformity

A circuit family $\{C_n\}$ is uniform if a classical polynomial-time Turing machine, on input $1^n$, outputs a description of $C_n$. Equivalently, the gate-by-gate specification of $C_n$ is computable in classical $\mathrm{poly}(n)$ time.

Without uniformity one gets non-uniform quantum complexity ($BQP/poly$ etc.); these classes are strictly larger (they contain undecidable languages, just like classical $P/poly$). All standard quantum complexity classes ($\mathsf{BQP}$, $\mathsf{EQP}$, $\mathsf{QMA}$, …) require uniformity.

So the classical Turing machine is still in the picture — but as a meta-machine generating the circuit description, not as the substrate of the quantum computation itself.

2.3 Universal gate sets

The set of all unitaries on $n$ qubits, $U(2^n)$, is a continuous group of real dimension $4^n$ — uncountable, so it cannot be generated by any finite gate set exactly. But finite gate sets can generate dense subgroups, and dense is good enough for any approximation tolerance.

A gate set $G$ is universal if its closure under composition is dense in $U(2^n)$ (or in $SU(2^n)$ — global phase is unobservable). Standard universal sets:

• $\{H,T,\mathrm{CNOT}\}$ — Hadamard, $\pi /8$-gate, controlled-NOT. The textbook universal set.
• $\{H,\mathrm{Toffoli}\}$ — Hadamard plus the classical 3-bit Toffoli (controlled-controlled-NOT). Universal for real-amplitude quantum computation, and universal over $\mathbb{C}$ for $\mathsf{BQP}$.
• $\{\text{Clifford}\}+T$ — Clifford gates ($H,S,\mathrm{CNOT}$) alone are not universal (Gottesman–Knill: efficiently classically simulable); adding the non-Clifford $T$ gate makes the set universal.

Solovay–Kitaev theorem (1995–97): for any universal gate set $G$ closed under inverses, any single-qubit unitary $U$ can be approximated to error $\epsilon$ in operator norm by a sequence of $O({\log }^c(1/\epsilon ))$ gates from $G$, with $c\approx 4$ (or $\approx 1$ for more refined modern variants). So "$O(f(n))$ gates" claims with a fixed universal gate set absorb $\mathrm{polylog}(1/\epsilon )$ overhead per approximated gate; for polynomial-time claims this is negligible.

This is why $\mathsf{BQP}$ is robust under choice of gate set: any two universal sets simulate each other with polylogarithmic overhead.

2.4 The quantum Turing machine

A quantum Turing machine (Deutsch 1985, formalized by Bernstein–Vazirani 1993) is a Turing machine whose configurations are vectors in a Hilbert space and whose transition function is a unitary on the configuration space. It is polynomially equivalent to the uniform circuit model: ${\mathsf{BQP}}_{\text{QTM}}={\mathsf{BQP}}_{\text{circuit}}$.

QTMs are almost never used to describe algorithms (the moving-head-in-superposition mechanics are awkward), but they appear in the foundational definition of $\mathsf{BQP}$ and in some proofs that benefit from a step-by-step time evolution.

2.5 The quantum query model

For oracle algorithms (Deutsch–Jozsa, Grover, Simon, Shor's period finding), the oracle is a unitary

$$U_f:|x⟩|y⟩⟼|x⟩|y\oplus f(x)⟩$$

implementing a classical function $f:\{0,1{\}}^n\to \{0,1{\}}^m$. Query complexity counts uses of $U_f$; the gates between queries are free. This is the quantum analogue of classical decision-tree complexity, and it gives the cleanest separations between classical and quantum (see § 4 and misc/deutsch-jozsa.md).

2.6 Measurement-based and adiabatic models

Two further models, polynomially equivalent to the circuit model (and so defining the same $\mathsf{BQP}$):

• Measurement-based quantum computing (one-way computer, Raussendorf–Briegel 2001): prepare a large entangled resource state (a cluster state), then perform a sequence of adaptive single-qubit measurements. The "program" is the measurement pattern.
• Adiabatic quantum computing (Farhi et al. 2000): slowly interpolate a Hamiltonian $H(t)=(1-t/T)H_0+(t/T)H_1$ between an easy ground state ($H_0$) and one encoding the answer ($H_1$); the spectral gap controls the required runtime.

Both are equivalent to the circuit model up to polynomial overhead. They differ in physical realizability and in algorithm-design idioms.

2.7 Cost-measure summary

All polynomially equivalent (where the question is well-posed), so $\mathsf{P}$ vs $\mathsf{BQP}$-style statements are model-independent. Constant factors and exact gate counts depend on the model and gate set.

3. Quantum Complexity Classes

3.1 The main definitions

The $2/3$ vs $1/3$ gap in $\mathsf{BQP}$, $\mathsf{QMA}$, etc. is amplifiable to $1-2^{-\mathrm{poly}(n)}$ by parallel repetition and majority vote, exactly as for $\mathsf{BPP}$ (Chernoff bound).

3.2 Known inclusions

$$\mathsf{P}\subseteq \mathsf{BPP}\subseteq \mathsf{BQP}\subseteq \mathsf{PP}\subseteq \mathsf{PSPACE},$$

$$\mathsf{NP}\subseteq \mathsf{QCMA}\subseteq \mathsf{QMA}\subseteq \mathsf{QIP}(3)=\mathsf{QIP}=\mathsf{PSPACE}.$$

Highlights worth knowing:

• $\mathsf{BQP}\subseteq \mathsf{PSPACE}$ (Bernstein–Vazirani 1993). Proof: compute $⟨y|U_T\cdots U_1|x⟩$ as a sum over $2^n$ paths (Feynman path integral), and the sum can be evaluated in polynomial space term by term. So a polynomial-time quantum computer is no more than polynomially-space-bounded classically.
• $\mathsf{BQP}\subseteq \mathsf{PP}$ (Adleman–DeMarrais–Huang 1997) and the sharper $\mathsf{BQP}\subseteq \mathsf{AWPP}\subseteq \mathsf{PP}$ (Fortnow–Rogers 1999).
• $\mathsf{QIP}=\mathsf{PSPACE}$ (Jain–Ji–Upadhyay–Watrous 2010). Quantum interaction does not exceed polynomial space — striking parity with classical $\mathsf{IP}=\mathsf{PSPACE}$.
• $\mathsf{QIP}(3)=\mathsf{QIP}$ (Kitaev–Watrous 2000): three rounds of quantum interaction suffice. Classically, $\mathsf{IP}$ requires polynomially many rounds.
• ${\mathsf{MIP}}^{\ast }=\mathsf{RE}$ (Ji–Natarajan–Vidick–Wright–Yuen 2020): multi-prover interactive proofs with entangled provers decide all r.e. languages — strictly more than classical $\mathsf{MIP}=\mathsf{NEXPTIME}$, and an outright separation from classical complexity. This resolved Connes' embedding conjecture in the negative.

3.3 Headline open questions

• $\mathsf{BPP}\stackrel{?}{=}\mathsf{BQP}$ — does quantum offer a super-polynomial speedup over randomized classical for any decision problem? (Believed false in some specific cases like factoring, but unproved.)
• $\mathsf{BQP}\subseteq \mathsf{NP}$? Almost certainly false (oracle-relative separations exist, see § 5), but no unconditional proof.
• $\mathsf{BQP}$ vs the polynomial hierarchy $\mathsf{PH}$: known oracle separations in both directions (Aaronson 2010; Raz–Tal 2019 — oracle separation ${\mathsf{BQP}}^O⊈{\mathsf{PH}}^O$).
• $\mathsf{QMA}\stackrel{?}{=}\mathsf{QCMA}$ — does a quantum witness give strictly more power than a classical one? Believed yes, but only oracle separations are known.
• $\mathsf{NP}\stackrel{?}{\subseteq }\mathsf{BQP}$ — can quantum computers solve $\mathsf{NP}$-complete problems in polynomial time? Believed firmly no; Grover gives only quadratic speedup ($O(\sqrt{N})$), and a matching lower bound (BBBV) rules out generic better-than-quadratic speedups in the black-box setting.

4. Quantum Query Complexity

For functions $f:\{0,1{\}}^N\to \{0,1\}$ given by an oracle, the quantum query complexity $Q(f)$ is the minimum number of queries to $U_f$ needed by any bounded-error quantum algorithm. This is the most-studied setting for proving unconditional quantum-classical separations.

4.1 Headline algorithms and bounds

The forrelation problem is the cleanest known way to separate $\mathsf{BQP}$ from $\mathsf{PH}$ in the oracle setting.

4.2 Lower-bound techniques

Two general methods produce unconditional quantum query lower bounds:

• Polynomial method (Beals–Buhrman–Cleve–Mosca–de Wolf 1998): the acceptance probability of any $T$-query quantum algorithm is a real polynomial in the oracle bits of degree $\le 2T$. Lower bounds on the approximate polynomial degree of $f$ thus give $Q(f)=\Omega (\widetilde{\mathrm{deg}}(f)/2)$.
• Adversary method (Ambainis 2000, with negative-weight refinement Høyer–Lee–Špalek 2007): a semidefinite program whose value characterizes $Q(f)$ exactly (up to constants). The negative-weight version gives tight lower bounds for all Boolean functions.

These are quantum-only tools — they have no classical analogue and are what makes the query setting so much cleaner than the time-complexity setting.

4.3 Polynomial vs. exponential speedup boundary

In the query model, quantum speedup over classical bounded-error algorithms is at most polynomial for total Boolean functions $f:\{0,1{\}}^N\to \{0,1\}$ (no promise):

$$R(f)=O(Q(f{)}^6)\text{(Aaronson–Ben-David–Kothari–Rao–Tal 2021)},$$

where $R(f)$ is randomized bounded-error query complexity. So exponential speedups require promise problems (Deutsch–Jozsa, Simon, Shor, forrelation), where the oracle is restricted to lie in a structured subset.

5. Oracle Results and Barriers

As with classical complexity (math/complexity-theory.md § 9), relativization gives evidence and barriers:

• $\exists O$: ${\mathsf{BQP}}^O⊈{\mathsf{PH}}^O$ (Raz–Tal 2019, via forrelation). Strong evidence that $\mathsf{BQP}$ is not contained in the polynomial hierarchy.
• $\exists O$: ${\mathsf{NP}}^O⊈{\mathsf{BQP}}^O$ (BBBV 1997 via the Grover lower bound — unstructured search needs $\Omega (\sqrt{N})$ quantum queries, so $\mathsf{NP}$ is not in $\mathsf{BQP}$ relative to a random oracle). Evidence that quantum computers can't solve $\mathsf{NP}$ in polynomial time.
• $\exists O$: ${\mathsf{P}}^O={\mathsf{BQP}}^O$ (trivial: use an oracle that derandomizes). So separating $\mathsf{P}$ from $\mathsf{BQP}$ unconditionally would require non-relativizing techniques.

Standard classical barriers — relativization, natural proofs, algebrization — apply to quantum-vs-classical separations as well, so an unconditional $\mathsf{BPP}\ne \mathsf{BQP}$ proof is currently out of reach.

6. Quantum Hamiltonian Complexity

A signature quantum-native complexity class is $\mathsf{QMA}$, and its prototypical complete problem is the Local Hamiltonian Problem — the quantum analogue of $k$-$\mathrm{SAT}$.

$k$-Local Hamiltonian Problem. Given a Hamiltonian $H={\sum }_i{H}_i$ on $n$ qubits where each $H_i$ acts non-trivially on at most $k$ qubits and $\Vert H_i\Vert \le 1$, and two thresholds $a<b$ with $b-a\ge 1/\mathrm{poly}(n)$, decide whether the ground-state energy of $H$ is $\le a$ or $\ge b$.

Kitaev's theorem (1999): the 5-local Hamiltonian problem is $\mathsf{QMA}$-complete. Subsequently improved to 2-local (Kempe–Kitaev–Regev 2006) and even physically realistic (1D, nearest-neighbor, fixed local dimension; Aharonov–Gottesman–Irani–Kempe 2009).

This is the "Cook–Levin theorem for quantum complexity". It says: even with quantum witnesses and verifiers, the hardest problems look like estimating ground-state energies of local quantum systems — exactly the central problem of condensed matter physics. The field of Hamiltonian complexity explores how quantum complexity classes relate to physical questions (entanglement structure of ground states, area laws, the quantum PCP conjecture).

The quantum PCP conjecture (Aharonov–Arad–Vidick) — a quantum analogue of the classical PCP theorem — is one of the major open problems of the field.

7. Specific Algorithms in the Circuit Model

This section briefly indexes the canonical quantum algorithms and their circuit-model resource costs. Pages for the individual algorithms can be added to the misc/ folder over time.

8. Pointers Onward

A non-exhaustive map of where quantum complexity theory goes from here:

• Quantum supremacy / advantage. Random Circuit Sampling, Boson Sampling, IQP — complexity-theoretically-justified candidates for tasks no classical computer can match in polynomial time. The 2019 Google "supremacy" experiment used Random Circuit Sampling.
• Quantum cryptography. $\mathsf{BQP}$-hardness of LWE (post-quantum lattice cryptography); $\mathsf{QMA}$-based protocols; quantum money; quantum-secure pseudorandomness.
• Quantum proofs and the certified-randomness pipeline. Mahadev's classical verification of quantum computations (2018) — a single quantum prover can be classically verified under cryptographic assumptions.
• Quantum communication and information complexity. Quantum communication can exponentially reduce protocol length for some tasks (Buhrman–Cleve–Wigderson).
• Quantum error correction and fault-tolerance are not strictly "complexity theory" but underpin the practical realization of $\mathsf{BQP}$: threshold theorem, surface codes, magic-state distillation.
• Quantum descriptive complexity, query lower-bound techniques, fine-grained quantum complexity.

For a systematic treatment see Watrous, The Theory of Quantum Information (Cambridge, 2018); Kitaev–Shen–Vyalyi, Classical and Quantum Computation (AMS, 2002); and the survey Aaronson, Quantum Computing Since Democritus (Cambridge, 2013).