Quantum Complexity

Complexity theory classifies problems by the resources needed to solve them. For quantum computers the resource is the number of elementary unitary gates (and qubits) required to achieve bounded error. The class BQP collects decision problems solvable in polynomial time on a quantum computer with error at most \(1/3\). It contains famous speedups (factoring via Shor; unstructured search via Grover) yet still sits inside PSPACE and is not known to contain NP-complete problems.

Verification brings QMA, the quantum analogue of NP: a “yes” instance admits a polynomial-size quantum state (a witness) that a polynomial-time quantum verifier accepts with high probability; “no” instances are rejected. The gap between BQP and QMA marks the difference between efficiently solving and efficiently checking — a split with physical interpretations in ground-state energy problems and error-correcting codes.

Key inclusions: \(\mathbf{P}\subseteq \mathbf{BPP}\subseteq \mathbf{BQP}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}\). Oracle results show separations in relativized worlds (e.g., there exists an oracle \(A\) with \(\mathbf{BQP}^A \not\subseteq \mathbf{PH}^A\)), suggesting quantum sampling tasks can outstrip the polynomial hierarchy. Postselection inflates power: PostBQP = PP, linking idealized nonphysical abilities to sharp jumps in complexity.

QMA contains problems like the Local Hamiltonian problem (Kitaev), the quantum analogue of SAT: given a sum of local terms \(H=\sum_j H_j\), decide whether the ground-state energy is \(\le a\) or \(\ge b\) for a gap \(b-a\ge 1/\text{poly}(n)\). This is QMA-complete even for 2-local interactions on qubits, tying condensed-matter physics directly to verification complexity.

Adiabatic quantum computation (AQC) evolves a ground state of \(H_0\) into that of \(H_1\) over time \(T\). It is polynomially equivalent to the circuit model, but performance depends on the minimum spectral gap along the path: \(T\propto \Delta_{\min}^{-2}\) (up to smoothness factors). Physically, this translates complexity into spectral engineering: bottlenecks are avoided crossings where many-body states nearly degenerate. Adiabatic algorithms for optimization are powerful but not panaceas — small gaps enforce long times.

Counting resources in real devices adds qubit overhead from error correction. Surface-code thresholds imply that logical gate counts inflate by polylogarithmic factors in target error, and magic-state distillation dominates cost for non-Clifford gates. Thus “polytime” can still mean enormous spacetime volumes; complexity theory sets asymptotic limits, engineering sets constants.

Quantum proofs differ because witnesses are states. QMA(2) allows two unentangled provers; power rises dramatically but enforcing “no entanglement” is subtle. Multi-prover interactive proofs with entanglement (MIP*) achieve surprising strength (even undecidable power), echoing the deep link between nonlocal games, operator algebras, and verification. For near-term devices, self-verification via randomized compiling, cross-entropy benchmarking, or interactive protocols (Mahadev-style classical verification of quantum computation) bridges theory and experiment.

Sampling complexity is another front: tasks like random circuit sampling or boson sampling are designed so that efficient classical simulation would collapse complexity hierarchies. While noise blunts the claim, robust average-case hardness conjectures underwrite the pursuit of quantum advantage benchmarks.

Quantum computers offer polynomial and sometimes superpolynomial speedups for structured problems (period finding, linear systems under promises, amplitude estimation). Yet generic NP-complete problems are not believed to fall into BQP; even quadratic speedups like Grover’s are optimal for unstructured search. Noisy devices must amortize error-correction overhead before large-scale algorithms are practical. Complexity theory is the map: it shows where speedups live, where barriers stand, and how physics (spectra, entanglement, noise) shapes the terrain.

The frontier blends physics with proofs: characterizing when local Hamiltonians have polynomial spectral gaps, bounding expressivity of shallow circuits, and understanding whether average-case versions of QMA-complete problems admit efficient quantum heuristics. Each result refines our sense of the limit of computational quantum power.