The Quantum Cook-Levin Theorem

The classical Cook-Levin theorem (1971) launched complexity theory by naming a single natural problem — Boolean satisfiability — that is complete for NP: every problem with an efficiently checkable proof reduces to it. The quantum descendant asks the same question one level up. QMA, Quantum Merlin-Arthur, is the class of decision problems whose YES instances carry a quantum witness state that a polynomial-time quantum verifier can check. Is there a natural problem complete for QMA, the way SAT is complete for NP? Kitaev's answer, worked out in the late 1990s and published in Kitaev-Shen-Vyalyi (2002), is yes: the local Hamiltonian problem, deciding whether the smallest eigenvalue of a sum of few-body Hermitian terms falls below a threshold $a$ or stays above $b$ , under the promise that one of these holds. This article is the flagship of the complexity head. The construction is a quantum tableau. Where Cook-Levin freezes the time-ordered configurations of a Turing machine into SAT clauses, Kitaev freezes the time-ordered states of a quantum circuit into a Hamiltonian, and the accepting computation becomes the ground state — the history state, a uniform superposition over every intermediate step tagged by a clock register. The Hamiltonian is four stacks of energy penalties: wrong input, illegal clock, incorrect gate propagation, and non-acceptance. Only a genuine accepting computation can near-annihilate all four at once. We build the map, prove membership and hardness, extract the inverse-cubic promise gap $b-a=\Theta(1/T^3)$ , and show why this one reduction founds the entire subject of quantum Hamiltonian complexity — the reason estimating ground-state energies is believed hard even for quantum computers.

Key takeaways

The Quantum Cook-Levin theorem (Kitaev): the $k$ -local Hamiltonian problem is QMA-complete — the quantum analogue of Cook-Levin's SAT is NP-complete.
The proof maps a verifier circuit $V=U_T\cdots U_1$ into a frustration-free Hamiltonian whose ground energy is small exactly when some witness makes $V$ accept with high probability.
The engine is the history state $|\eta\rangle=\tfrac{1}{\sqrt{T+1}}\sum_{t=0}^{T}U_t\cdots U_1|\xi\rangle\otimes|t\rangle$ , a uniform superposition over the whole computation, encoded in a clock register.
Kitaev's original construction is $5$ -local; Kempe-Kitaev-Regev (2006) tightened it to $2$ -local, and Aharonov-Gottesman-Irani-Kempe (2007) to a 1D chain.
The promise gap scales as $b-a=\Theta(1/T^3)$ : the clock-Laplacian spectral gap $\sim 1/T^2$ times the output weight $\sim 1/T$ , inverse-polynomial but enough for QMA membership.
Key idea: encode an entire quantum computation as the ground state of a local Hamiltonian — penalize wrong inputs, illegal clock states, incorrect gate propagation, and non-acceptance — so the minimum energy is low exactly when an accepting witness exists.

The core insight

Encode an entire quantum computation as the ground state of a local Hamiltonian: penalize wrong inputs, illegal clock states, incorrect gate propagation, and non-acceptance, so that the minimum eigenvalue is low exactly when an accepting witness exists — making the local Hamiltonian problem QMA-complete.

Where this lives today

The theorem is the load-bearing wall of quantum Hamiltonian complexity, where much of quantum computing meets physics. Its message — that computing a generic local Hamiltonian's ground energy is QMA-hard — is why quantum chemistry and condensed-matter simulation have no known efficient general algorithm even quantumly, funnelling practical effort into structured instances, variational methods, and heuristics such as VQE and phase estimation on near-term hardware. The classification programme of Cubitt and Montanaro, extended by Bausch, Piddock and others, now sorts physical interaction families — Heisenberg, Ising-with-fields, Bose-Hubbard — into "QMA-complete" versus "efficiently solvable," a quantum echo of Schaefer's dichotomy for classical CSPs. The gadget technology that pushed Kitaev's $5$ -local terms to $2$ -local and onto lattices is reused wholesale in adiabatic quantum computation and quantum-annealer embedding. And the frontier keeps climbing the proof hierarchy the theorem began, from QMA to QMA(2) to the resolution of $\mathsf{MIP}^\ast=\mathsf{RE}$ , each leaning on the same intuition: a computation can be pinned down as a constraint on states.

The physical picture

Picture a quantum computation as a movie reel. Classical Cook-Levin checks it with Boolean clauses — one for the first frame, one for every transition, one for the final frame — so the formula is satisfiable exactly when a legal accepting film exists. Kitaev does identical bookkeeping with energy instead of logic: a penalty for a wrong first frame, for every bad transition, for a rejecting last frame. But quantum mechanics forbids pointing at a single "current frame" to copy — no-cloning rules it out — so he stores the whole reel in superposition at once: the history state, a uniform sum over all $T+1$ steps, each snapshot paired with a clock label $|t\rangle$ . The first figure lays out this tableau and its four penalty stacks.

Figure

Kitaev's circuit-to-Hamiltonian tableau: the history state is a uniform superposition over T+1 clock-tagged frames, each frame the circuit state Uₜ···U₁ applied to the input ξ. Four penalty stacks — H_in fixes the input frame, H_prop links neighbours by Uₜ, H_clock forbids illegal clock labels, H_out reads the output at t = T. For T = 100 and acceptance p = 0.99 the history-state energy equals (1−p)/(T+1) = 9.9×10⁻⁵

The locality is the whole trick. A unary clock writes time $t$ as $|1^t0^{T-t}\rangle$ , so a propagation penalty reads off "we are at step $t$ " by inspecting just three neighbouring clock qubits — the domain wall between ones and zeros — and checks gate $U_t$ by touching the at-most-two qubits it acts on. Five qubits: the term is $5$ -local, exactly the resource a physical Hamiltonian is allowed. The second figure is the spectral heart of soundness: unfolded onto the valid subspace, the propagation Hamiltonian is half the graph Laplacian of a path of $T+1$ clock sites, whose eigenvalues form a cosine band whose tiny bottom gap sets the promise.

Figure

The propagation spectrum on the valid history subspace: H_prop is unitarily equivalent to half the Laplacian of a path of T+1 clock sites, with eigenvalues E_k = 1 − cos(πk/(T+1)) forming a cosine band from 0 to 2. The history state is the unique zero mode. The smallest nonzero gap Δ₁ = 1 − cos(π/(T+1)) ≈ π²/2(T+1)² = 4.84×10⁻⁴ for T = 100 sets the 1/T² factor behind the promise gap

The reduction runs both ways, and the second is hard. Completeness is nearly free: an accepting witness gives a history state of tiny energy, because the input, clock, and propagation stacks are frustration-free — the history state sits in all three kernels — so only the output stack contributes. Soundness is subtle: any low-energy state, computation-like or not, must be close to a genuine history state of some input, where its rejecting weight cannot hide. The device converting "low energy" into "almost a real computation" is the Projection Lemma, and the resulting gap is exactly the cosine-band gap diluted by the output weight.

The core equations

The problem itself is a promise problem about a Hermitian operator built from few-body pieces. We are handed a sum of local terms and asked which side of a gap its ground energy lies on; the gap is only guaranteed inverse-polynomial, which is precisely what makes the question non-trivial.

L_a^b=\Big\{\,H=\textstyle\sum_{j=1}^{m}H_j\ :\ \lambda_{\min}(H)\le a\ \ \text{or}\ \ \lambda_{\min}(H)\ge b,\ \ b-a\ge 1/\mathrm{poly}(n)\,\Big\} \qquad (1)

where: $H_j$ — a Hermitian term acting nontrivially on at most $k$ qubits, with $\lVert H_j\rVert\le\mathrm{poly}(n)$ ; $m$ — the number of terms, polynomial in $n$ ; $\lambda_{\min}(H)$ — the smallest eigenvalue, i.e. the ground-state energy; $a,b$ — the YES and NO thresholds, separated by an inverse-polynomial promise gap $b-a$ . Reading it: decide whether the ground energy is low ( $\le a$ , a YES instance) or high ( $\ge b$ , a NO instance), promised it is never in between. The witness that makes a YES instance's energy low is the history state — the uniform superposition over every step of the verifier, each snapshot paired with its clock label. It is the quantum stand-in for Cook-Levin's satisfying tableau.

|\eta\rangle=\frac{1}{\sqrt{T+1}}\sum_{t=0}^{T}\big(U_t\cdots U_1|\xi\rangle\big)\otimes|t\rangle \qquad (2)

where: $|\xi\rangle$ — the input register, the quantum witness qubits together with ancillas fixed to $|0\cdots0\rangle$ ; $U_t$ — the $t$ -th one- or two-qubit gate of the verifier; $|t\rangle$ — the clock register encoding step $t$ , for $t=0,\dots,T$ ; $T$ — the number of gates, polynomial in $n$ . Reading it: the state carries the entire computation at once, weighted equally across time, so measuring the clock and finding $t$ collapses the register to exactly the $t$ -th intermediate state. Each propagation term forces frame $t$ to be the correct gate image of frame $t-1$ . It is a projector onto the anti-symmetric combination of two adjacent frames, so the correctly propagated (symmetric) combination costs zero energy.

H_{\mathrm{prop},t}=\tfrac12\Big(I\otimes|t\rangle\langle t|+I\otimes|t\!-\!1\rangle\langle t\!-\!1|-U_t\otimes|t\rangle\langle t\!-\!1|-U_t^\dagger\otimes|t\!-\!1\rangle\langle t|\Big) \qquad (3)

where: $U_t$ — the gate applied at step $t$ , acting on the computational register; $|t\rangle\langle t\!-\!1|$ — the clock transition operator advancing $t-1\to t$ ; $I$ — identity on the computational register. Reading it: on the two-dimensional block spanned by $\{|\psi_{t-1}\rangle|t\!-\!1\rangle,\,U_t|\psi_{t-1}\rangle|t\rangle\}$ this acts as $\tfrac12\!\left(\begin{smallmatrix}1&-1\\-1&1\end{smallmatrix}\right)$ , a rank-one projector with eigenvalues $\{0,1\}$ — energy $0$ for correct propagation, $1$ for a broken link. The full Kitaev Hamiltonian stacks four families of penalties. Three of them (input, clock, propagation) are simultaneously satisfiable by any history state; only the fourth, the output check, resists.

H=H_{\mathrm{in}}+H_{\mathrm{clock}}+H_{\mathrm{prop}}+H_{\mathrm{out}},\qquad H_{\mathrm{prop}}=\sum_{t=1}^{T}H_{\mathrm{prop},t} \qquad (4)

where: $H_{\mathrm{in}}$ — penalizes any ancilla not in $|0\rangle$ at clock time $0$ ; $H_{\mathrm{clock}}$ — penalizes illegal unary-clock patterns such as $|\dots01\dots\rangle$ ; $H_{\mathrm{prop}}$ — the sum of propagation terms enforcing gate-by-gate evolution; $H_{\mathrm{out}}$ — penalizes the designated output qubit reading $|0\rangle$ (reject) at clock time $T$ . Reading it: the ground state must fix the input, respect the clock, obey the gates, and accept — only a real accepting computation escapes every penalty. The output term is the one that carries the energy scale. Evaluated on a history state it picks out only the final frame, weighted by that frame's share $1/(T+1)$ of the uniform superposition, and reports the circuit's rejection probability.

H_{\mathrm{out}}=|0\rangle\langle0|_{\mathrm{out}}\otimes|T\rangle\langle T|,\qquad \langle\eta|H_{\mathrm{out}}|\eta\rangle=\frac{1-p_{\mathrm{acc}}}{T+1} \qquad (5)

where: $|0\rangle\langle0|_{\mathrm{out}}$ — projector onto the rejecting value of the output qubit; $p_{\mathrm{acc}}=\lVert\Pi_1 U_T\cdots U_1|\xi\rangle\rVert^2$ — the witness's acceptance probability; $1/(T+1)$ — the weight of the final clock step. Reading it: a perfectly accepting witness ( $p_{\mathrm{acc}}=1$ ) gives exactly zero energy; every unit of rejection probability costs $1/(T+1)$ of energy, spread thin across the long computation. The two thresholds follow. YES instances (accepting witness) sit at energy $\le a$ ; NO instances (no witness accepts well) are pushed up to $\ge b$ , and the separation is the cosine-band gap diluted by the output weight.

\text{YES}:\ \lambda_{\min}(H)\le a=\frac{\varepsilon}{T+1};\qquad \text{NO}:\ \lambda_{\min}(H)\ge b=a+\frac{c}{T^{3}},\qquad b-a=\Theta\!\big(1/T^{3}\big) \qquad (6)

where: $\varepsilon$ — the verifier completeness error, so $p_{\mathrm{acc}}\ge1-\varepsilon$ on YES instances; $c$ — a universal constant from the Projection-Lemma analysis; $1/T^3$ — the inverse-cubic gap, from the clock-Laplacian gap $\Theta(1/T^2)$ times the output weight $\Theta(1/T)$ . Reading it: the gap shrinks polynomially with circuit length, but stays $1/\mathrm{poly}$ , which is all QMA membership needs.

Derivation AThe history state is a zero-energy eigenstate of the propagation Hamiltonian

The goal is to prove the frustration-free backbone of the whole construction: that the input, clock, and propagation terms all annihilate the history state simultaneously, so that on a YES instance the only surviving energy comes from the single output term. This is what turns a messy sum of non-commuting projectors into a clean instrument whose ground energy tracks one quantity — the circuit's rejection probability — and it is the reason completeness costs almost nothing while all the difficulty is pushed into soundness.

Step 1. Expand a single propagation term on the history state. Because $|\eta\rangle$ already pairs $U_t\cdots U_1|\xi\rangle$ with $|t\rangle$ and $U_{t-1}\cdots U_1|\xi\rangle$ with $|t-1\rangle$ , the four pieces of $H_{\mathrm{prop},t}$ act inside the two-frame block $\{|\psi_{t-1}\rangle|t\!-\!1\rangle,\,U_t|\psi_{t-1}\rangle|t\rangle\}$ where $|\psi_{t-1}\rangle=U_{t-1}\cdots U_1|\xi\rangle$ . Why: the term only sees clock labels $t-1$ and $t$ , so its action on the full superposition reduces to a $2\times2$ computation.

Step 2. On that block $H_{\mathrm{prop},t}=\tfrac12\!\left(\begin{smallmatrix}1&-1\\-1&1\end{smallmatrix}\right)$ , whose kernel is the symmetric vector $\tfrac{1}{\sqrt2}(|\psi_{t-1}\rangle|t\!-\!1\rangle+U_t|\psi_{t-1}\rangle|t\rangle)$ . The two adjacent frames of the history state enter with equal amplitude $1/\sqrt{T+1}$ , i.e. in exactly the symmetric combination, so $H_{\mathrm{prop},t}|\eta\rangle=0$ . Why: the uniform weighting of the history state is not decorative — it is what places $|\eta\rangle$ in every propagation kernel; any other weighting would cost energy.

Step 3. Sum over $t$ : $H_{\mathrm{prop}}|\eta\rangle=\sum_{t=1}^{T}H_{\mathrm{prop},t}|\eta\rangle=0$ , so the history state lies in the common kernel of all propagation terms. Add the input and clock terms: at $t=0$ the ancillas are $|0\rangle$ by construction of $|\xi\rangle$ , so $H_{\mathrm{in}}|\eta\rangle=0$ ; every clock label $|1^t0^{T-t}\rangle$ is a legal unary pattern, so $H_{\mathrm{clock}}|\eta\rangle=0$ . Why: three of the four stacks vanish, isolating the physics into the fourth.

Step 4. Only $H_{\mathrm{out}}$ remains. Projecting onto $t=T$ leaves $H_{\mathrm{out}}|\eta\rangle=\tfrac{1}{\sqrt{T+1}}|0\rangle\langle0|_{\mathrm{out}}U_T\cdots U_1|\xi\rangle\otimes|T\rangle$ , so $\langle\eta|H_{\mathrm{out}}|\eta\rangle=\tfrac{1}{T+1}\lVert|0\rangle\langle0|_{\mathrm{out}}U_T\cdots U_1|\xi\rangle\rVert^2=\tfrac{1-p_{\mathrm{acc}}}{T+1}$ . Why: this is the entire YES-case energy — proportional to how badly the witness fails to accept, and to nothing else. *To summarise the four steps: the $2\times2$ block of $H_{\mathrm{prop},t}$ has eigenvalues $\{0,1\}$ ; the history state lies in the common kernel of $H_{\mathrm{in}}+H_{\mathrm{clock}}+H_{\mathrm{prop}}$ ; and $\langle\eta|H_{\mathrm{out}}|\eta\rangle=(1-p_{\mathrm{acc}})/(T+1)$ , which for $T=100,\,p_{\mathrm{acc}}=0.99$ gives $0.01/101=9.9\times10^{-5}$ .*

Go deeper · Derivation B · 2 minThe local Hamiltonian problem belongs to QMA

Derivation BThe local Hamiltonian problem belongs to QMA

The goal is to show that a low-energy state is an efficiently checkable quantum witness, so the problem lies in QMA and the reduction has an upper bound to match its hardness. The idea is that a quantum verifier need not diagonalize $H$ ; it can estimate the energy of a single randomly chosen local term, and by linearity the average of these local energies equals the total energy divided by the number of terms. This converts a global eigenvalue question into a local measurement, which is exactly what a poly-time quantum machine can perform.

Step 1. Merlin sends a state $|\psi\rangle$ on $n$ qubits, claimed to be a ground state of $H$ . Arthur first shifts each term so that $0\preceq H_j\preceq\Lambda I$ with $\Lambda=\max_j\lVert H_j\rVert$ , which only translates the spectrum and rescales the thresholds. Why: a measurement outcome must be a probability in $[0,1]$ , so each local term has to be normalized into a valid POVM before it can be sampled.

Step 2. Arthur picks $j\in\{1,\dots,m\}$ uniformly, measures the observable $H_j/\Lambda$ on the $\le k$ relevant qubits, and rejects with probability equal to that outcome. The chance of rejecting on term $j$ is $\langle\psi|H_j|\psi\rangle/\Lambda$ . Why: sampling a random term and reading its normalized energy makes the expected penalty a faithful, unbiased probe of the local energy.

Step 3. Average over the uniform choice: $\Pr[\text{accept}]=\tfrac1m\sum_j\big(1-\tfrac{\langle\psi|H_j|\psi\rangle}{\Lambda}\big)=1-\tfrac{\langle\psi|H|\psi\rangle}{m\Lambda}$ . Why: linearity of expectation collapses $m$ local measurements into one statement about the global energy $\langle\psi|H|\psi\rangle$ — the verifier learns the total without ever holding the whole operator.

Step 4. Split the promise. A YES instance ( $\lambda_{\min}\le a$ ) admits a witness accepted with probability $\ge1-\tfrac{a}{m\Lambda}$ ; a NO instance ( $\lambda_{\min}\ge b$ ) forces acceptance $\le1-\tfrac{b}{m\Lambda}$ for every state. The gap is $\tfrac{b-a}{m\Lambda}$ , inverse-polynomial. Why: an inverse-polynomial separation is enough for QMA, because it is the amplifiable regime — a negligible gap would not be.

Step 5. Amplify by parallel repetition: $O(\mathrm{poly})$ independent copies with a majority vote drive the two-sided error below any $2^{-m}$ , all in polynomial time. Hence a poly-time quantum verifier with a quantum witness decides the promise, so the local Hamiltonian problem is in QMA. Why: robustness of the threshold is what lets a $1/\mathrm{poly}$ gap stand in for a constant one, completing membership. *To summarise: after shifting each term so that $0\preceq H_j\preceq\Lambda I$ , the inverse-polynomial gap $b-a\ge1/\mathrm{poly}$ survives amplification. As a concrete check, $m=100,\ \Lambda=1,\ a=0.1,\ b=0.2$ give an acceptance gap $(b-a)/(m\Lambda)=10^{-3}$ .*

Go deeper · Derivation C · 2 minSoundness and the inverse-cubic promise gap

Derivation CSoundness and the inverse-cubic promise gap

The goal is the hard direction: if no witness makes the verifier accept well, then every state has energy at least $b$ , with $b-a=\Omega(1/T^3)$ . The danger is a state that is not a genuine history — one that satisfies propagation only partway and dodges the output penalty. The Projection Lemma rules this out by confining any low-energy state to the neighbourhood of the valid history subspace, where the clock-Laplacian spectrum forces a definite energy cost proportional to the circuit's best rejection probability. This is what makes the reduction QMA-hard rather than merely a membership statement.

Step 1. Scale the constraint terms: replace $H_{\mathrm{in}}+H_{\mathrm{clock}}+H_{\mathrm{prop}}$ by $J(H_{\mathrm{in}}+H_{\mathrm{clock}}+H_{\mathrm{prop}})$ for a large $J=\mathrm{poly}(T)$ . Their common ground space $\mathcal{S}_{\mathrm{valid}}$ is exactly the set of history states of arbitrary inputs $|\xi\rangle$ . Why: making the constraints stiff means any cheap state must nearly satisfy them, so the only affordable states look like real computations.

Step 2. Apply the Projection Lemma (Kempe-Kitaev-Regev): any state of energy $\ll J$ is $O(1/\sqrt{J})$ -close to $\mathcal{S}_{\mathrm{valid}}$ , and the true ground energy of $H$ equals the ground energy of $H_{\mathrm{out}}$ restricted to $\mathcal{S}_{\mathrm{valid}}$ , up to $O(1/\sqrt{J})$ corrections. Why: this is the geometric engine — it certifies that "low energy" implies "almost a valid history", so a non-history evasion of $H_{\mathrm{out}}$ is impossible.

Step 3. Restrict $H_{\mathrm{out}}$ to $\mathcal{S}_{\mathrm{valid}}$ . On the history state of input $|\xi\rangle$ its expectation is $\tfrac{1-p_{\mathrm{acc}}(\xi)}{T+1}$ , minimized over inputs at the best acceptance $p_{\max}$ : the reduced operator is $\succeq\tfrac{1}{T+1}(1-p_{\max})$ times a spectral factor. Why: within the valid subspace, minimizing energy is minimizing rejection over all inputs, so no witness escapes its own acceptance bound.

Step 4. Diagonalize $H_{\mathrm{prop}}$ on the valid subspace: it is unitarily equivalent to half the path Laplacian, with eigenvalues $1-\cos\frac{\pi k}{T+1}\sim\frac{\pi^2k^2}{2(T+1)^2}$ . The smallest nonzero mode, gap $\Theta(1/T^2)$ , controls how a low-energy trial state can spread over the clock and dilute the output penalty. Why: this cosine band is where the $1/T^2$ enters; the output weight $1/T$ multiplies it, producing the $1/T^3$ scaling.

Step 5. Combine: if $p_{\max}\le1-\delta$ then $\lambda_{\min}(H)\ge b$ with $b-a=\Omega(1/T^3)$ . Since Cook-Levin-style verifiers can be error-reduced so $p_{\max}$ is bounded away from $1$ on NO instances, the promise gap is genuine and the reduction is complete: local Hamiltonian is QMA-hard, hence QMA-complete. Why: a bona-fide $1/\mathrm{poly}$ gap on both sides is exactly the QMA-completeness certificate. *To summarise: the $1/T^3$ promise gap decomposes as (clock-Laplacian gap $\Theta(1/T^2)$ ) × (output weight $\Theta(1/T)$ ), with the propagation eigenvalues given by $1-\cos\frac{\pi k}{T+1}$ . For $T=100$ the smallest nonzero gap is $\Delta_1=1-\cos(\pi/101)=4.84\times10^{-4}\approx\pi^2/2(101)^2$ .*

Limiting cases

Pushing the construction's parameters to their extremes exposes what each piece is doing — and where later work moved the frontier.

Case	Result	Meaning
Perfect acceptance	$\lambda_{\min}(H)=0$ , $a=0$	if some witness makes $V$ accept with probability $1$ , the history state sits in every kernel including $H_{\mathrm{out}}$ ; the YES threshold can be taken to be exactly zero (frustration-free)
Long circuits	$b-a=\Theta(1/T^3)$	the promise gap shrinks polynomially with circuit length $T$ , but verification stays poly-time, so QMA membership is preserved
Locality reduction	$5\text{-local}\to 2\text{-local}$	Kempe-Kitaev-Regev perturbative gadgets cut $k$ down to $2$ at the cost of larger norms and a smaller effective gap; QMA-completeness survives
Geometry	line / 2D lattice	Aharonov-Gottesman-Irani-Kempe (1D, larger qudits) and Oliveira-Terhal (2D qubit grid) show hardness persists for nearest-neighbour terms
Stoquastic / sign-free	class $\mathsf{StoqMA}$	removing the sign problem (all off-diagonal terms $\le 0$ ) drops the problem to a class believed weaker than QMA — the hardness needs genuine quantum phase

Common trapThe history-state ground energy is zero

It is not, unless acceptance is perfect. The input, clock, and propagation terms are frustration-free and the history state lies in their common kernel — but the output term contributes a residual $\tfrac{1-p_{\mathrm{acc}}}{T+1}$ , which vanishes only when $p_{\mathrm{acc}}=1$ . Confusing "frustration-free propagation" with "zero total ground energy" collapses the gap analysis, because the whole reduction lives in the difference between the YES energy $\varepsilon/(T+1)$ and the NO energy $\varepsilon/(T+1)+c/T^3$ . A related trap: the $2\times2$ propagation block has eigenvalues $\{0,1\}$ , so $H_{\mathrm{prop}}$ is a sum of projectors, but its restriction to the valid subspace is not a projector — it is half a graph Laplacian, and its small nonzero eigenvalues (not a gap of $1$ ) set the promise. Treating $H_{\mathrm{prop}}$ as constant-gapped overestimates the promise gap by powers of $T$ .

Worked examples

1 · Locality and ground energy of a concrete Kitaev Hamiltonian (fully worked)

A verifier circuit has $T=100$ gates acting on qubits with a unary clock. A claimed witness makes it accept with probability $p_{\mathrm{acc}}=0.99$ . Count the locality of a propagation term, compute the history-state energy (the YES threshold), and compare it to the NO-side gap.

Step 1. Count the locality. A single propagation term $H_{\mathrm{prop},t}$ reads the clock only through $|t\rangle\langle t\!-\!1|$ , which in the unary (domain-wall) encoding inspects the three clock qubits at positions $t\!-\!1,t,t\!+\!1$ to locate the wall, and acts on the computational register only through $U_t$ , which touches at most $2$ qubits. Total: $3+2=\mathbf{5}$ qubits — the term is $5$ -local, matching Kitaev's original construction.

Step 2. Compute the YES energy. By the frustration-free result, $H_{\mathrm{in}}$ , $H_{\mathrm{clock}}$ , $H_{\mathrm{prop}}$ all annihilate the history state, so $\langle\eta|H|\eta\rangle=\langle\eta|H_{\mathrm{out}}|\eta\rangle=\tfrac{1-p_{\mathrm{acc}}}{T+1}=\tfrac{1-0.99}{101}=\tfrac{0.01}{101}=\mathbf{9.9\times10^{-5}}$ . This is the threshold $a$ : the ground energy of a YES instance is at most this.

Step 3. Estimate the NO-side gap. The clock-Laplacian gap is $\Delta_1=1-\cos\frac{\pi}{T+1}=1-\cos\frac{\pi}{101}\approx\frac{\pi^2}{2(101)^2}=\mathbf{4.84\times10^{-4}}$ . The promise gap is this $\Theta(1/T^2)$ factor diluted by the output weight $\Theta(1/T)$ , giving $b-a=\Theta(1/T^3)\sim 10^{-6}$ up to the universal constant.

Step 4. Read the moral. The energies are tiny and the YES/NO separation is even tinier, but all are $1/\mathrm{poly}(T)$ , so a QMA verifier estimating a random local term still resolves the promise after polynomially many repetitions. Result: the term is 5-local, the YES ground energy is $9.9\times10^{-5}$ , and the promise gap is $\Theta(1/T^3)$ , set by the clock gap $4.84\times10^{-4}$ .

2 · From local Hamiltonian energy to a QMA acceptance probability (fully worked)

A $5$ -local Hamiltonian has $m=100$ terms, each shifted to $0\preceq H_j\preceq\Lambda I$ with $\Lambda=1$ . The promise is $a=0.1$ (YES) versus $b=0.2$ (NO). Find the verifier's acceptance probabilities and the number of repetitions to reach error $2^{-10}$ .

Step 1. Acceptance formula. Arthur measures a random normalized term, so $\Pr[\text{accept}]=1-\tfrac{\langle\psi|H|\psi\rangle}{m\Lambda}=1-\tfrac{\langle\psi|H|\psi\rangle}{100}$ . The ground-state witness makes $\langle\psi|H|\psi\rangle=\lambda_{\min}$ .

Step 2. Evaluate both cases. YES ( $\lambda_{\min}\le0.1$ ): $\Pr[\text{accept}]\ge1-\tfrac{0.1}{100}=\mathbf{0.999}$ . NO ( $\lambda_{\min}\ge0.2$ ): $\Pr[\text{accept}]\le1-\tfrac{0.2}{100}=\mathbf{0.998}$ . The raw gap is $\delta=(b-a)/(m\Lambda)=0.1/100=\mathbf{10^{-3}}$ .

Step 3. Amplify. A gap of $10^{-3}$ around a shifted midpoint is inverse-polynomial; by the Chernoff bound the majority of $k$ runs errs with probability $\le e^{-2k\delta^2}=e^{-2k\times10^{-6}}$ . To beat $2^{-10}$ needs $k\ge\frac{10\ln2}{2\times10^{-6}}\approx\mathbf{3.5\times10^{6}}$ runs — polynomial in the problem size, as required.

Step 4. Interpret. The verifier never diagonalizes $H$ ; it samples one $5$ -qubit measurement per run and votes. That a mere $10^{-3}$ acceptance gap certifies membership is the entire content of "inverse-polynomial gap suffices for QMA". Result: YES accepts with $\ge0.999$ , NO with $\le0.998$ , gap $10^{-3}$ , amplified to $2^{-10}$ error in $\approx3.5\times10^6$ poly-time runs.

Physics of the portrait

The local Hamiltonian problem is where computational complexity and condensed-matter physics turned out to be the same subject. The person who welded them together also built the toolkit — the surface code, anyons, phase estimation — that most of quantum computing now runs on.

Origins · 1 minAlexei Kitaev and how this was discovered

Alexei Kitaev

born 1963, quantum computation and topological phases of matter · creator of the circuit-to-Hamiltonian construction and the quantum Cook-Levin theorem

Alexei Kitaev, trained at the Landau Institute and now at Caltech, has a habit of reframing quantum computing so completely that the old questions dissolve. In the late 1990s, after Bernstein and Vazirani had defined BQP and others were circling QMA, he asked: is there a natural QMA-complete problem, a quantum SAT? His answer, the local Hamiltonian problem, came bundled with the construction that proves it — the history-state Hamiltonian, first circulated in lectures and written up fully in the 2002 book with Shen and Vyalyi. The move is audacious: he takes a dynamical object, a circuit unfolding in time, and freezes it into a static ground-state problem, so "does this computation accept?" becomes "is this energy low?". The same period produced his other landmarks — the toric code and topological quantum computation (1997), quantum phase estimation, the Solovay-Kitaev theorem — and the local Hamiltonian result quietly seeded a whole field, quantum Hamiltonian complexity, that Kempe, Regev, Aharonov, Oliveira, Terhal, Cubitt, Gharibian and others have mapped ever since. Where Cook and Levin gave classical complexity its first complete problem, Kitaev gave the quantum theory of ground states its foundation stone.

History

1971

— Cook proves Boolean satisfiability is NP-complete, with Levin independently in 1973

1985

— Deutsch defines the quantum Turing machine, seeding a complexity theory of quantum computation

1999

— Kitaev introduces the local Hamiltonian problem and proves the 5-local case QMA-complete

2002

— Kitaev, Shen and Vyalyi publish the full history-state construction and Projection Lemma

2006

— Kempe, Kitaev and Regev reduce the hardness to 2-local Hamiltonians

2007

— Aharonov, Gottesman, Irani and Kempe prove QMA-completeness on a 1D chain

Going further

Texts. Kitaev, Shen & Vyalyi, Classical and Quantum Computation (2002), Ch. 14 · Kempe, Kitaev & Regev, "The Complexity of the Local Hamiltonian Problem," SIAM J. Comput. 35 (2006) · Aharonov & Naveh, "Quantum NP — A Survey" (2002) · Watrous, The Theory of Quantum Information (2018) · Gharibian, Huang, Landau & Shin, "Quantum Hamiltonian Complexity," Found. Trends TCS (2015) · Cook, "The Complexity of Theorem-Proving Procedures," STOC 1971. The key numerical anchors of the construction are: (1) each $H_{\mathrm{prop},t}$ has eigenvalues $\{0,1\}$ from its $2\times2$ block, and the clock-Laplacian spectrum is $1-\cos\frac{\pi k}{T+1}$ ; (2) the residual output energy is $\tfrac{1-p_{\mathrm{acc}}}{T+1}$ , giving $9.9\times10^{-5}$ at $T=100,\ p_{\mathrm{acc}}=0.99$ ; (3) the $\Theta(1/T^3)$ promise gap equals (clock gap $\Theta(1/T^2)$ , numerically $4.84\times10^{-4}$ at $T=100$ ) × (output weight $\Theta(1/T)$ ); (4) the membership acceptance probability is $\Pr=1-\langle\psi|H|\psi\rangle/(m\Lambda)$ , with a $10^{-3}$ gap for $m=100,\ \Lambda=1,\ a=0.1,\ b=0.2$ .

Prerequisites. Quantum Merlin-Arthur (QMA) · The Local Hamiltonian Problem · The Complexity Class BQP. Leads to. QMA Variants and Related Classes · Quantum Interactive Proofs (QIP) · MIP* = RE.

Ask the tutor: Ask me to walk through why the history state annihilates three of the four penalty stacks, to trace the clock-Laplacian spectrum behind the $1/T^3$ gap, or to compare Kitaev's construction line-by-line with the classical Cook-Levin tableau.

How is this really the quantum version of Cook-Levin?

Structurally they are the same proof in two languages. Cook-Levin takes an NP verifier and encodes its space-time tableau into SAT: clauses for the initial configuration, for each legal transition, and for an accepting final state, so the formula is satisfiable exactly when a valid accepting run exists. Kitaev takes a QMA verifier and encodes its history into a Hamiltonian: an input term, propagation terms per gate, a clock term, and an output term, so the ground energy is low exactly when an accepting run exists. Both yield a single natural problem — SAT, local Hamiltonian — complete for the relevant verification class. The change from "satisfiable" to "low energy" is the change from classical to quantum witnesses.

Why must the witness be stored in superposition instead of frame by frame?

Because there is no classical "current frame" to copy forward. In Cook-Levin the tableau lists every configuration explicitly as bits, so a clause can compare frame $t$ with frame $t+1$ . A quantum computation has no such transcript: no-cloning forbids duplicating an unknown intermediate state, so you cannot lay the frames out as independent registers. Kitaev's fix is to keep the single evolving state, tag it with a clock, and take a uniform superposition over all clock values; the propagation term then compares the two clock-adjacent branches of that one superposition. The history state is the only object that both respects quantum mechanics and lets a local term check a global time-ordering.

What is the clock register and why does it make the terms local?

The clock makes "which time step" a locally readable quantity. In the unary encoding, time $t$ is $t$ ones followed by $T-t$ zeros, $|1^t0^{T-t}\rangle$ , so the boundary between ones and zeros — the domain wall — sits at position $t$ . A propagation term acting "at step $t$ " just finds that wall by inspecting three neighbouring clock qubits, then applies gate $U_t$ to its two computational qubits: five qubits total. Without a clock, "apply gate $t$ next" is a global statement about the whole computation that no few-body operator can enforce. The clock is precisely the device that localizes time.

Does QMA-completeness mean quantum computers cannot do quantum chemistry?

Not in the defeatist sense. The theorem says that in the worst case, estimating a general local Hamiltonian's ground energy is QMA-hard, so no algorithm — classical or quantum — solves every instance efficiently unless $\mathsf{BQP}=\mathsf{QMA}$ (widely disbelieved). But real molecules are not worst-case: they carry structure, symmetry, locality, and often a spectral gap, and many such families are tractable or well-approximated by heuristics like the variational quantum eigensolver, tensor networks, or phase estimation on a good initial state. The result is a map of where the hard instances live, not a verdict that chemistry is hopeless — it tells practitioners to exploit structure rather than chase a universal fast algorithm that provably cannot exist.

Why is the Projection Lemma needed, and what would break without it?

Completeness is easy — exhibit the history state and read off its energy — but soundness has to rule out impostors. A malicious state might satisfy the propagation constraints only approximately, drifting away from the valid history subspace so it never fully weights the rejecting final frame, faking low energy on a NO instance. The Projection Lemma forbids this: once the constraint terms are scaled up, any state of energy well below that scale is geometrically close (within $O(1/\sqrt{J})$ ) to a genuine history state, so its energy is governed by the output term restricted to real histories. Without it, "low energy" would not imply "close to an accepting computation," and the $\Omega(1/T^3)$ NO-side bound — the thing that makes the reduction hard — would collapse.

How did the locality get pushed from 5-local to 2-local and onto a line?

Through gadget constructions that trade locality for overhead. Kempe-Kitaev-Regev (2006) introduced perturbative gadgets: an ancilla with a strong local field, coupled weakly, generates an effective $k$ -body interaction at second or third order in perturbation theory, simulating a $5$ -local term with $2$ -local ones at the price of larger norms and a smaller gap. Oliveira and Terhal then embedded such $2$ -local terms onto a 2D qubit grid. Aharonov-Gottesman-Irani-Kempe (2007) reached a 1D chain by enlarging the local space to qudits of dimension around $12$ , with a clock and propagation rules living entirely on nearest neighbours. Each step keeps QMA-completeness while making the Hamiltonian look more like something a physicist could build.