Can a physical system that just relaxes into its ground state be as powerful as a full quantum circuit, and how far can "squeeze a decision into an energy gap" be pushed before nobody knows the answer?
Topics 16–17 built VQE: a loop that always reports an energy honestly no lower than the truth, because the variational principle proves it. What that loop does not come with is a promise that it ever finds the true ground energy in reasonable time, on a general Hamiltonian. This section asks the question directly: exactly how hard is "find this Hamiltonian's ground energy," as a decision problem, and does the answer explain, rather than just describe, why every near-term algorithm on this page ships without a speed guarantee?
The adiabatic theorem, a genuinely old fact from ordinary quantum mechanics, says a system that starts in a Hamiltonian's ground state and has that Hamiltonian deformed slowly enough stays in the ground state throughout. It "rides along" rather than getting kicked into an excited state. Farhi, Goldstone, Gutmann & Sipser (arXiv quant-ph/0001106, 2000) turned this into a proposed computing model: start a physical system in the easy-to-prepare ground state of a simple Hamiltonian H₀, slowly deform it toward a "problem Hamiltonian" HP whose ground state encodes an answer, and just let physics do the rest.
The obvious question is whether this is a genuinely different, perhaps weaker, model of computation than the circuit model this whole page has otherwise used, or the same power in different clothes. It's the same clothes: topic 19's history-state Hamiltonian is exactly the kind of object this model needs, because its ground state already is the record of a circuit's computation. Aharonov, van Dam, Kempe, Landau, Lloyd & Regev proved the adiabatic model is polynomially equivalent to the standard circuit model: anything BQP can compute, adiabatic evolution can too, with only polynomial overhead, and vice versa.
For H(s) = (1−s)H₀ + sHP, s going from 0 to 1 over total time T, the adiabatic theorem guarantees the system tracks the ground state provided T is large enough relative to how small the spectral gap gets along the path: the smaller the minimum gap, the longer the sweep must run. Verified directly on topic 19's own toy Hamiltonian: with H₀ built so its unique, trivially-prepared ground state is the simple product state |0⟩⊗|clock=0⟩, and HP the exact history-state Hamiltonian from topic 19 (minimum spectral gap along the path: 0.134), a real time-evolved sweep gives a final-state fidelity with the true history-state ground state of 0.3845 at T=2, climbing to 0.5630 (T=5), 0.8156 (T=10), 0.9902 (T=25), and 0.9989 (T=60): monotonically converging toward the exact answer as the sweep slows down, exactly as the theorem predicts. (This uses a simplified stand-in H₀ for clarity; the published proof's own initial Hamiltonian is a little more elaborate, also clock-based, so that its ground state can be checked cheaply too: the mechanism being demonstrated here is identical.) Aharonov, van Dam, Kempe, Landau, Lloyd & Regev, SIAM J. Comput. 37(1), 166 (2007), arXiv quant-ph/0405098. Kempe, Kitaev & Regev's own 2-local paper (topic 19) proved the same equivalence holds even restricted to 2-local interactions: the locality reduction and the adiabatic-universality result come from the same techniques, in the same paper.
The quantum PCP conjecture: the open question this machinery leads to. Classically, the PCP theorem (Arora & Safra, J. ACM 45(1), 70 (1998); Arora, Lund, Motwani, Sudan & Szegedy, J. ACM 45(3), 501 (1998)) says NP-hardness survives even when a solution only needs to be approximately satisfying: e.g. it's NP-hard to tell whether a 3-SAT instance is fully satisfiable or at most a constant fraction of its clauses can ever be satisfied at once, a gap that scales with the size of the instance rather than shrinking. The quantum PCP conjecture (Aharonov, Arad & Vidick, ACM SIGACT News 44(2), 47 (2013), arXiv 1309.7495) asks whether the local Hamiltonian problem is QMA-hard even to that same coarse, extensive precision (a constant fraction of the total energy scale) rather than only the 1/poly(n) precision topics 18–19 actually proved hardness for. Nobody knows. The obstruction is genuinely quantum: classical hardness-of-approximation proofs amplify a small gap into a large one by taking many independent copies of an instance, but a quantum witness's copies can be entangled with each other in ways that let a clever Merlin cheat a naive amplification scheme: the same no-cloning-flavoured obstruction topic 18 raised for QMA's own error bounds, one level higher up. One necessary consequence of the conjecture, the NLTS ("no low-energy trivial states") property, was proven true in 2022 (Anshu, Breuckmann & Nirkhe, STOC 2023, arXiv 2206.13228, from good quantum LDPC codes): a real, checked result, and honestly stated: necessary for quantum PCP to hold, not sufficient to prove it. The conjecture itself remains open.
Why "the annealer works, sometimes" isn't a contradiction of anything proven here The physical quantum annealers on compare.html use exactly this adiabatic idea, but run far faster and hotter than the provably-safe adiabatic regime this topic describes: a deliberate engineering trade-off, not a violation of the theorem, and the honest reason that section already states plainly that a physical annealer solves one problem shape and offers no universal speed guarantee. And if the quantum PCP conjecture ever were resolved affirmatively, it would sharpen exactly what topics 16–17 already say about VQE and QAOA from the other direction: not just "nobody has proven a speedup," but a proof that no efficient quantum algorithm (not just the ones tried so far) can approximate some ground energies well, full stop.
Check yourself
What does the adiabatic theorem require of a sweep for the system to stay in the ground state?
Slower sweeps converge on the true ground state, exactly as measured on the same toy Hamiltonian: fidelity 0.38 at T = 2 climbing to 0.999 at T = 60.