27. Computational Complexity
27.1P
P is the class of decision problems solvable in polynomial time — where the exponent is a fixed constant and the input size n is the variable. Sorting, shortest paths, primality (AKS, 2002), linear programming: all in P. "Polynomial" is the field's formalization of "scalable": O(n²) may be painful, but O(2ⁿ) is hopeless, and there is no natural class in between. The pragmatist's caveat, which you should never forget: a "polynomial" O(n¹⁰⁰) algorithm is worthless, and hardware constants matter — P is a statement about asymptotic existence, and engineering (Part XII) is about the constants P ignores. Quantum complexity inherits every one of these caveats.
27.2NP
NP: problems whose yes answers have short certificates you can verify quickly — finding the certificate may be hard, checking it is easy. SAT, factoring-as-decision, Hamiltonian cycles, all of optimization's hardest darlings. NP-complete problems (Cook–Levin: SAT is universal) are the hardest in NP; solving one in polynomial time solves all of them. Two clarifications the popular press gets wrong constantly: NP does not mean "non-polynomial," and P vs NP is open — decades of effort, proof barriers (relativization, natural proofs, algebrization) catalogued, no resolution. Whether quantum computers touch NP is a precise, answerable question — see 27.10 — and the answer is the most-quoted negative result in the field.
27.3Polynomial Time
Why worship polynomials? Three reasons. Closure: polynomials compose — a poly-time subroutine called poly-times stays poly, which is what lets complexity classes be closed under reduction. Robustness: the class is invariant under every reasonable machine model (RAM, Turing, λ-calculus — the Church–Turing thesis' quantitative cousin, the "extended Church–Turing thesis," is exactly the claim that quantum machines also don't change it — and Shor is the counterexample-in-waiting). Honesty: asymptotics encode the only insight that survives hardware churn. The engineer's translation: complexity classes tell you which battles are worth fighting; the exponent and constants tell you whether you'll win this year.
27.4Exponential Time
EXP and friends: solvable with 2^poly(n) resources. Every problem is decidable in EXP, most interesting problems have exponential brute-force fallbacks, and the whole drama of algorithms is the gap between EXP and P. Quantum computing enters as a partial shrinker of that gap: Grover gives a generic √ speedup on any search-shaped problem (2ⁿ → 2^(n/2)), which is real and universal and — this is the letdown — nowhere near collapsing EXP to P. The structural lesson: quantum speedups are not one phenomenon; generic search speedup (quadratic), structural speedup (exponential, but only for problems with the right hidden algebra), and sampling speedups are three different animals. Part 28 taxonomizes them.
27.5Reductions
A reduction is a translation: problem A reduces to B if a B-solver gives you an A-solver with polynomial overhead. It is complexity theory's only microscope — direct proofs of hardness are beyond current techniques, but reductions propagate difficulty across the map. For you: when someone claims quantum speedup for problem X, your first question is "reduced from what, or to what?" Reduction from a known-hard problem suggests depth; reduction to a known-easy structure is where quantum speedup claims usually die (the structured instance may be classically easy for reasons the reducer never checked). Reduction literacy is the difference between reading a quantum-advantage paper and being read by it.
27.6Complexity Classes
The map, honestly drawn: P ⊆ BQP ⊆ PSPACE (proven); NP ⊆ PSPACE; whether BQP intersects NP-hard territory: unknown and believed mostly no (for decision problems); P vs BQP: open — Shor is evidence of separation, not proof. Add the quantum-flavored siblings: QMA (quantum certificates — the class of ground-state-energy problems, 28.6), QIP, BQC (verified delegated computation). The picture to keep: quantum computing carves sideways through the map — taking problems believed classical-hard (factoring, which sits in NP∩co-NP, outside believed-P but not NP-complete) into BQP, while leaving NP-complete problems standing.
27.7BQP
BQP: problems solvable on a quantum computer in polynomial time, with error probability ≤ 1/3, uniformly. The definition's moving parts deserve attention: bounded error (amplifiable by repetition to 1/3ᵏ — the machinery of Part VII's repetition arguments), uniformity (one algorithm family, not per-input advice), polynomial in n qubits and time. Everything on IBM's and Google's roadmaps is an attempt to build a physical BQP machine at scale; everything in Part VII is BQP's greatest hits. The class is robust to the gate set (any reasonable universal set gives the same BQP) and to modest noise assumptions — which is what makes it an engineering target at all.
27.8Quantum Speedups
Taxonomy before enthusiasm. Exponential, structural: factoring, discrete log, phase-estimation-flavored problems — require hidden algebraic structure; the speedup comes from the QFT revealing periodicity (Ch. 23). Quadratic, generic: Grover/amplitude amplification — works on any search, guaranteed, and quadratic is provably optimal for black-box search (BBBV bound). Sampling: random circuit sampling, boson sampling — provable separations under complexity assumptions, but verification is itself hard. Simulation: quantum chemistry, materials — Feynman's original proposal; the speedup claim rests on representing a quantum system with a quantum system. Four different beasts; four different evidence standards; all four get marketed identically, which is exactly why you need the taxonomy.
27.9Oracle Separations
The field's main proof technology, and its most misused. An oracle O is a black-box function; a separation relative to O shows that with O given for free, quantum machines solve some task in fewer queries than classical ones. Simon's oracle separation (1994) directly inspired Shor. But separations relative to an oracle do not separate the classes themselves — the oracle may bake the structure in. TheBBBV theorem shows oracles where Grover's quadratic is optimal; recursive oracles (Aaronson–Kuperberg) separate QMA from QCMA both ways. Rule: oracle results are evidence about technique, not about the world. When a paper headlines an oracle separation, appreciate it, then ask what happens with the oracle instantiated.
27.10What Quantum Computing Does Not Prove
The negative results are as load-bearing as the positive ones. One: BQP ⊆ PSPACE — quantum computers do not beat all classical computation, only efficient classical computation. Two: no known speedup for NP-complete problems; Grover's quadratic is the ceiling for unstructured search, and BBBV says no quantum trick beats it. Three: no-cloning forbids "try all answers in parallel and read them out" — the misunderstanding underlying half of all overclaims. Four: P vs NP and P vs BQP remain open; Shor's algorithm is a pointer, not a proof. Five: sampling speedups rest on unproven complexity assumptions. Fluency in these five is your defense against both hype and its overcorrection.