6 min read
On this page

Quantum Complexity Theory

BQP: Bounded-Error Quantum Polynomial Time

BQP is the class of decision problems solvable by a polynomial-time quantum Turing machine with error probability at most 1/3. This is the quantum analogue of BPP.

Formal definition: Language L is in BQP if there exists a uniform family of polynomial-size quantum circuits {C_n} such that for input x of length n:

  • x in L implies Pr[C_n accepts x] >= 2/3
  • x not in L implies Pr[C_n accepts x] <= 1/3

Error can be amplified to 2^{-poly(n)} by O(poly(n)) repetitions and majority vote.

Known inclusions:

  • P subset BPP subset BQP subset PSPACE
  • BQP subset PP (Adleman-DeMarrais-Huang)
  • BQP does not contain NP-complete problems relative to a random oracle (with high probability)
  • Integer factoring and discrete logarithm are in BQP (Shor's algorithm) but believed not in BPP

BQP vs. PH: Relative to an oracle, BQP is not contained in PH (Raz-Tal 2019), providing strong evidence that quantum computers solve problems outside the polynomial hierarchy.

QMA: Quantum Merlin-Arthur

QMA is the quantum analogue of NP (or more precisely, MA). A language L is in QMA if there exists a polynomial-time quantum verifier V such that:

  • Completeness: x in L implies there exists a quantum witness |psi> on poly(n) qubits such that V accepts with probability >= 2/3
  • Soundness: x not in L implies for all quantum witnesses |psi>, V accepts with probability <= 1/3

QMA-complete problems:

  • Local Hamiltonian Problem (Kitaev): Given a k-local Hamiltonian H = sum H_i, determine whether the ground state energy is below a or above b (with b - a >= 1/poly(n)). This is the quantum analogue of SAT. QMA-complete for k >= 2.
  • Consistency of Local Density Matrices
  • Quantum Satisfiability (k-QSAT for k >= 3)

Variants:

  • QMA(2): Two unentangled quantum provers. Potentially more powerful than QMA; the pure state N-representability problem is QMA(2)-complete.
  • QCMA: Classical witness, quantum verifier. QMA contains QCMA contains MA, but separations are unknown unconditionally.

QIP: Quantum Interactive Proofs

QIP(k) denotes k-round quantum interactive proof systems. The landmark result:

QIP = PSPACE (Jain-Ji-Upadhyay-Watrous 2011)

Key intermediate results:

  • QIP(k) = QIP(3) for all constant k >= 3 (quantum message compression)
  • QIP(1) = QMA
  • QIP(2) already captures powerful problems

This means quantum interactive proofs are no more powerful than classical interactive proofs (IP = PSPACE), though they may use fewer rounds.

PostBQP = PP

PostBQP is BQP with postselection -- the ability to condition on specific measurement outcomes (even exponentially unlikely ones).

Theorem (Aaronson 2005): PostBQP = PP.

This is a cornerstone result connecting quantum computation to classical counting complexity. Consequences:

  • If BQP = PostBQP, then the polynomial hierarchy collapses (strong evidence that quantum mechanics cannot be efficiently classically simulated)
  • Provides tools for proving quantum supremacy results
  • PP is closed under intersection (Beigel-Reingold-Spielman), so PostBQP inherits this

Quantum Supremacy

Quantum computational supremacy (or quantum advantage): demonstrating that a quantum device performs a computational task infeasible for any classical computer.

Requirements: The task must be (1) efficiently performed by a quantum computer, (2) classically intractable, and (3) verifiable.

Theoretical foundation: If the output distribution of polynomial-depth quantum circuits could be sampled classically in polynomial time, then the polynomial hierarchy would collapse to the third level. This follows from the PostBQP = PP connection and complexity-theoretic arguments.

Random Circuit Sampling

Google's Sycamore experiment (2019, 53 qubits): Sample from the output distribution of random quantum circuits. Classical simulation estimated at ~10,000 years; quantum device performed in ~200 seconds.

The complexity argument relies on:

  • Porter-Thomas distribution: Output probabilities of random circuits follow an exponential distribution
  • Cross-entropy benchmarking (XEB): Measures fidelity by comparing observed bitstring frequencies against ideal probabilities
  • Anti-concentration: Random circuits produce sufficiently spread-out distributions

Caveats: Classical simulation algorithms have improved significantly since the original claim; the precise boundary of classical intractability remains debated.

Boson Sampling

Proposed by Aaronson and Arkhipov (2011). n identical photons input into an m-mode linear optical network. The output distribution is governed by permanents of submatrices of the m x m unitary, and computing permanents is #P-hard.

Complexity argument: Exact classical simulation implies P^{#P} = BPP^{NP}, collapsing the polynomial hierarchy. Approximate simulation under plausible conjectures (permanent anti-concentration and average-case hardness) also implies PH collapse.

Gaussian Boson Sampling (GBS): Uses squeezed states instead of single photons. Implemented by USTC's Jiuzhang (2020, 76 photons). Relation to graph problems (hafnians instead of permanents).

Quantum Query Complexity

Studies the number of queries to an oracle (black box) needed to solve a problem. Provides the cleanest separations between classical and quantum computation.

Polynomial Method (Beals-Buhrman-Cleve-Mosca-de Wolf)

Theorem: If a quantum algorithm makes T queries to compute a Boolean function f, then f can be represented as a multilinear polynomial of degree at most 2T over the reals.

This lower bound technique works by showing that the acceptance probability is a polynomial of bounded degree in the input variables. Applications:

  • Grover's search: Omega(sqrt(N)) queries (matching upper bound)
  • OR function: quantum degree >= n/2, so Q(OR) >= n/2... but actually quantum query complexity is Theta(sqrt(n)) via more refined analysis
  • Parity requires n/2 quantum queries (matches classical -- no quantum speedup for parity)

Adversary Method

Original adversary method (Ambainis): Construct a relation R between positive and negative inputs. Lower bound depends on how well any single query can "distinguish" related pairs.

Negative weights adversary (Hoyer-Lee-Spalek): Uses a positive semidefinite adversary matrix Gamma. The bound is: Q(f) >= ||Gamma|| / max_i ||Gamma_i||

where Gamma_i zeros out entries distinguished by querying variable i.

Theorem (Reichardt): The general adversary bound is tight -- it exactly characterizes quantum query complexity (up to constant factors) for all Boolean functions. This is proven via the connection to span programs and quantum walks.

Key Separations

| Problem | Classical | Quantum | Separation | |---------|-----------|---------|------------| | Unstructured search | Theta(N) | Theta(sqrt(N)) | Quadratic | | Period finding | Theta(sqrt(N)) | O(1) | Exponential | | Element distinctness | Theta(N) | Theta(N^{2/3}) | Polynomial | | Graph connectivity | Theta(N^2) | Theta(N^{3/2}) | Polynomial | | Formula evaluation | Theta(N) | Theta(sqrt(N)) | Quadratic | | Forrelation | Theta(sqrt(N)) | O(1) | Exponential (total function) |

Forrelation (Aaronson-Ambainis) provides the maximal quantum-classical separation for total Boolean functions: O(1) quantum queries vs Omega(sqrt(N)/log N) classical. This connects to the oracle separation BQP not in PH.

Quantum Communication Complexity

Studies communication needed between parties to compute joint functions on distributed inputs.

  • Quantum communication can provide at most polynomial savings over classical communication for total functions (Kremer's theorem)
  • Exponential separations exist for partial functions (e.g., disjointness: quantum Theta(sqrt(n)) vs classical Theta(n))
  • Entanglement can reduce communication (but not beyond sqrt(n) for set disjointness)
  • Quantum fingerprinting achieves exponential savings for the equality function in simultaneous message passing