Is the local Hamiltonian problem actually as hard as anything in QMA, and can you watch the reduction work on a circuit small enough to check by hand?
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 classical Cook–Levin theorem reduces any NP verifier's computation to a SAT instance: build one Boolean variable per bit of every step of the computation, and one clause per rule the computation must obey (this gate's output follows from its inputs; the last step accepts). Kitaev's construction: sometimes called the quantum Cook–Levin theorem: does the same job for QMA, but the "encode the whole computation as one object" trick has to become genuinely quantum, because a quantum computation is a superposition evolving through time, not a single deterministic trace.
The object that does it is the history state: instead of picking one moment of the computation, superpose every moment at once, each tagged by a "clock" register recording which step it is. Build a Hamiltonian whose terms penalize (a) a malformed clock, and (b) any step where the data register's content doesn't match what the verifier circuit's next gate should have produced from the previous step. A state gets low energy from this Hamiltonian if and only if it looks like a real, correctly-computed history of some run of the circuit, and if the verifier circuit accepts with high probability on some witness, the true history state built from that witness has energy at (or near) the true minimum. That correspondence (accepting computation ⟺ low ground energy) is the entire proof.
For a circuit applying gates U₁,…,UT to a data register, with a clock register of T qubits in "unary" form (clock value t is represented as t ones followed by T−t zeros), the Hamiltonian is H = Hclock + Hin + Hprop, where Hclock penalizes any clock string that isn't a valid unary count, Hin penalizes the wrong data value at clock=0, and each propagation term is
Ht = ½( I⊗(Pt−1+Pt) − Ut⊗|t⟩⟨t−1| − Ut†⊗|t−1⟩⟨t| )
where Pt projects the clock onto its valid t-th value. Built and diagonalized exactly, not just described: for the 1-qubit, 2-gate toy circuit in the figure (apply H, then Z, to data qubit |0⟩), this Hamiltonian is an 8×8 matrix (1 data + 2 clock qubits). Exact diagonalization gives ground energy 0.0000000000 and a ground state whose overlap with the constructed history state (|0⟩|00⟩+|+⟩|10⟩+|−⟩|11⟩)/√3 is 1.0000000000 to machine precision: the ground state is the history state, not merely close to it, with a real spectral gap of 0.134 above it separating it from every other configuration. (Without Hin, this ground space is 2-dimensional: spanned by the histories of every possible starting data value, which is itself worth stating plainly: Hin is what pins the reduction to one specific input rather than "some input or other." A verification script recomputes it.)
The locality this construction needs, and how far it's been pushed down. This toy example's terms touch at most 3 qubits (1 data + 2 clock) because its gates are single-qubit and its clock is short, but a construction robust to any circuit (multi-qubit gates, arbitrarily long clocks, checked only via local clock-adjacency) needs more room. Kitaev's original proof used 5-local terms (Kitaev, Shen & Vyalyi, 2002). Kempe & Regev reduced this to 3-local (Quantum Inf. Comput. 3(3), 258 (2003), arXiv quant-ph/0302079). Kempe, Kitaev & Regev pushed it to 2-local using "perturbative gadgets": auxiliary qubits with large coupling constants whose low-energy effective behaviour approximates a higher-local term (SIAM J. Comput. 35(5), 1070 (2006), arXiv quant-ph/0406180). 1-local Hamiltonian is not QMA-complete. Each term acts on a single qubit independently, so the ground energy is just the sum of each term's own lowest eigenvalue, achievable by an unentangled product state and found in polynomial time; it's in P, believed strictly easier than QMA-complete problems.
The same Hamiltonian that proves hardness also turns out to be preparable a completely different way Nothing about the history-state Hamiltonian above is specific to verifying a circuit after the fact. It's a genuine, physical local Hamiltonian, meaning something else can ask about it: what if, instead of diagonalizing it on paper, you built a physical system with exactly this Hamiltonian and let it relax into its own ground state? That question (and a real, surprising answer) is next.
Check yourself
In Kitaev's construction, what is the ground state of the history-state Hamiltonian for the toy circuit?
Exact diagonalisation gives ground energy 0 and a ground state whose overlap with the history state is 1: it is the history state, not merely close to it.