28. Where Quantum Speedups Actually Come From
28.1Brute-Force Misconceptions
The most damaging sentence in quantum computing: "it tries all 2ⁿ answers in parallel." If that were the mechanism, we'd collapse NP overnight — measure the satisfying assignment out of the superposition. We can't, because measurement samples the distribution we built, and building the right distribution is the problem. Parallelism in superposition is free; reading anything useful out costs. Every real speedup works not by trying more, but by arranging interference so that the answer's amplitude is large at measurement time — a constraint-driven optimization, not a brute-force windfall. Kill this misconception now; it will otherwise resurface in every meeting you ever sit in.
28.2Interference
The universal mechanism. A quantum computation is a choreography of amplitudes: paths from input to wrong answers acquire phases that cancel; paths to right answers reinforce. Deutsch's algorithm is the minimal demonstration — one query, two paths, one destructive interference. Grover is the industrial version: reflect about the mean, reflect about the marked state, rotate amplitude where you want it, 2ⁿ/² times. QFT is interference as readout: phases accumulated along a register recombine into a period estimate. The design question is never "how do I try everything?" but "which phases do I kick where so the histogram ends up peaked?" — and that question has only a handful of known answering techniques.
28.3Amplitude Amplification
The one generic primitive: given a checking procedure (oracle) and any preparation of a search space, amplify the good amplitude quadratically faster than random sampling — O(√(N/M)) queries for M marked items, provably optimal. Its generalizations cover most "quantum speedup" proposals in the wild: quantum counting (estimating M), fixed-point search, amplitude estimation (Monte Carlo with √ advantage — finance's favorite claim, Ch. 50), and boosting. Its limits are equally generic: quadratic only, oracle cost counts, and the input must be preparable. When evaluating any proposed quantum algorithm, locate it relative to amplitude amplification first; most are it, wearing a costume.
28.4Hidden Structure
Exponential speedups live here, and the gate is narrow: the problem must contain algebraic structure that the QFT can expose — periodicity (Shor: f(x+r) = f(x)), hidden subgroup (the generalization; efficient for abelian groups, open for non-abelian — which is why graph isomorphism and lattice problems remain classical-side), hidden shift, phase estimation of accessible unitaries. Note what's absent: no NP-complete problem is known to reduce to a hidden-subgroup problem over an abelian group. The engineering moral: exponential quantum advantage is rare and structural, not a general-purpose accelerant. Roadmap claims of "exponential speedup for your industry" should be audited against this gate.
28.5Sampling Problems
Provable separations without structure: sample from distributions that are easy to prepare quantumly and believed hard classically. Random circuit sampling (Google 2019), boson sampling (photonic), IQP circuits. The evidence standard: separation holds under complexity assumptions (polynomial hierarchy doesn't collapse) and the verification story is statistical (XEB), not absolute — critics like Kalai have pushed hard on exactly this. Practical payoff is currently nil: the distributions sampled have no known use. The scientific payoff is enormous: these are the only controlled experiments testing whether BQP machines outperform classical ones at all. Read supremacy-era papers as physics experiments with complexity-theory error bars.
28.6Simulation Problems
Feynman 1982: nature isn't classical, so simulate physics with quantum machinery. This is the most defensible speedup class because it requires no hidden algebra — representing an n-body quantum system's state classically costs exponential space by construction (Part V!), while 2n qubits do it natively. Quantum chemistry (ground-state energies for catalysis, Ch. 48), materials (high-Tc superconductors), nuclear and condensed-matter dynamics, and — increasingly — quantum-enhanced verification of quantum hardware itself. The catch is precision: chemical accuracy needs error correction at scale, which is why simulation is the roadmap application, not the NISQ one. Ch. 48 gives the honest state of play.
28.7Algebraic Structure
Zoom out and the pattern sharpens: every exponential speedup runs through algebra — Fourier transforms over groups, periodicity, eigenvalue access. This is both a map (where to hunt for new algorithms: quantum walk on structures, linear-systems problems with structured oracles — HHL's caveats being the cautionary tale, Ch. 49) and a wall (structureless problems are quantumly boring: BBBV). The dequantization saga is the wall in motion: Tang's 2019 classical algorithm ate the claimed speedups for recommendation-systems-flavored linear algebra by exploiting the same structure classically plus sample access. Current best practice: assume every structure-based quantum claim has a classical competitor until you've checked the last five years of literature.
28.8Quantum Complexity Theory
The living theory beyond BQP: QMA (quantum NP — local Hamiltonians are QMA-complete; the quantum chemistry "hard even for quantum computers in the worst case" caveat), QQC and adiabatic classes, query-complexity lower bounds (polynomial method, adversary method — the tools that prove Grover optimal), and the interplay with cryptography (lattices resist known quantum attacks — post-quantum crypto's foundation, Ch. 46). If research calls to you (Part XIV), this is the subfield where a software engineer's skill at implementation and empiricism meets open theory: lower-bound techniques in particular are under-explored computationally, and machine-assisted proof is young.
28.9Practical vs Asymptotic Speedup
The final filter. Asymptotic: for large enough n, quantum wins. Practical: at the sizes anyone cares about, on real hardware, with error-correction overhead included. The gap between them is where careers and companies have been lost. Concretely: Shor's asymptotic advantage is exponential, but factoring RSA-2048 needs ~4,000 logical qubits and ~10⁹ logical gates — a machine that doesn't exist yet (Starling-class, ~2029+, and Starling targets 100 logical qubits, not 4,000). Grover vs AES-128 needs ~3,000 logical qubits running 2⁶⁴ iterations for days. The honest analysis every engineer owes their stakeholders: pipeline the whole stack — algorithm → logical qubits → physical qubits → hours → dollars — before quoting any speedup. Part XIX builds that spreadsheet.