Local Hamiltonian is QMA-complete

Inclusion · quantum setting · KSV02

Statement

Given $H={\sum }_i{H}_i$ on $n$ qubits with $\mathrm{poly}(n)$ terms, each acting on at most $k$ qubits and of norm at most $\mathrm{poly}(n)$, and thresholds $a<b$ with $b-a\ge 1/\mathrm{poly}(n)$, the local Hamiltonian problem with locality $k$ asks whether the ground-state energy of $H$ is at most $a$ or at least $b$, promised one holds. For every constant $k\ge 5$ it is in QMA and QMA-hard, hence QMA-complete — KSV02.

Sketch

Containment: the verifier picks a term $H_i$ at random and measures the witness against it, rejecting with probability proportional to its energy; the gap between the cases is inverse-polynomial, and QMA error reduction amplifies it. Hardness: the Feynman–Kitaev clock construction encodes a QMA verifier circuit into a local Hamiltonian whose low-energy states are history states, superpositions over the computation’s time steps, so ground energy below the threshold certifies an accepting witness.

Notes

• The problem remains QMA-complete for $k=3$ — KR03 — and for $k=2$, via perturbation-theory gadgets — KKR06.