The Local Hamiltonian Problem

If $\mathsf{NP}$ has $\mathsf{SAT}$ as its canonical complete problem, $\mathsf{QMA}$ has the local Hamiltonian problem. It is the quantum generalization of constraint satisfaction, and Kitaev's proof of its $\mathsf{QMA}$ -completeness is the cornerstone result connecting computational complexity to condensed-matter physics: estimating the ground-state energy of a realistic quantum system is, in the worst case, as hard as anything a quantum verifier can check.

The problem statement

A $k$ -local Hamiltonian on $n$ qubits is a sum

H = \sum_{j=1}^{m} H_j,

where each term $H_j$ is Hermitian, acts nontrivially on at most $k$ of the $n$ qubits, has $\|H_j\| \le 1$ , and $m = \mathrm{poly}(n)$ . The decision problem $k$ - $\mathrm{LH}$ takes such an $H$ together with two thresholds $a < b$ with a gap $b - a \ge 1/\mathrm{poly}(n)$ , and asks about the smallest eigenvalue $\lambda_{\min}(H)$ — the ground-state energy:

\text{YES: } \lambda_{\min}(H) \le a, \qquad \text{NO: } \lambda_{\min}(H) \ge b.

The promise gap $b - a$ plays the role of the bounded-error gap and must shrink no faster than inverse polynomially. Intuitively this asks: does there exist a state of energy below $a$ , or is every state above $b$ ?

It is in QMA

Membership is the easy and physically transparent direction. The witness is a claimed low-energy state $\ket{\psi}$ . Arthur estimates its energy $\bra{\psi} H \ket{\psi} = \sum_j \bra{\psi} H_j \ket{\psi}$ by picking a random term $H_j$ , measuring the corresponding $k$ -qubit observable, and averaging. Because each $H_j$ acts on only $k$ qubits and $\|H_j\|\le 1$ , each measurement is efficient, and the empirical mean estimates the energy to inverse-polynomial accuracy with bounded error. A true ground state passes when $\lambda_{\min} \le a$ (completeness); when $\lambda_{\min} \ge b$ , no state can register an energy below $b$ (soundness), because $\bra{\psi} H \ket{\psi} \ge \lambda_{\min}$ for every $\ket{\psi}$ . Hence $k$ - $\mathrm{LH} \in \mathsf{QMA}$ .

It is QMA-hard: Kitaev's circuit-to-Hamiltonian construction

The deep direction is hardness: every $\mathsf{QMA}$ problem reduces to local Hamiltonian. Given a verifier circuit $V_x = U_T \cdots U_1$ of $T = \mathrm{poly}$ gates, Kitaev builds a Hamiltonian whose ground state is forced to encode the entire history of a valid accepting computation,

\ket{\eta} = \frac{1}{\sqrt{T+1}} \sum_{t=0}^{T} \big(U_t \cdots U_1 \ket{\psi}\ket{0}\big)\otimes \ket{t}_{\text{clock}},

with the time step $t$ stored in a clock register. The Hamiltonian is a sum of local penalty terms:

H = H_{\text{in}} + H_{\text{out}} + H_{\text{prop}} + H_{\text{clock}}.

$H_{\text{in}}$ penalizes any ancilla not initialized to $\ket{0}$ at clock time $0$ .
$H_{\text{prop}} = \sum_t H_{\text{prop},t}$ penalizes any history state whose step $t \to t{+}1$ does not apply the correct gate $U_t$ — it enforces the circuit's dynamics.
$H_{\text{out}}$ penalizes a non-accepting output at the final clock time.
$H_{\text{clock}}$ penalizes illegal clock encodings.

Each term is local. The point is that a state can have low total energy only if it is (close to) the history state of a genuine, accepting run of $V_x$ on some witness — so $\lambda_{\min}$ is small exactly when Merlin had a witness Arthur would accept. Bounding the spectral gap of $H_{\text{prop}}$ (a quantum walk on the clock line) supplies the $1/\mathrm{poly}$ promise gap. This reduction proves $k$ - $\mathrm{LH}$ is $\mathsf{QMA}$ -hard, hence $\mathsf{QMA}$ -complete.

Why physicists care

The local Hamiltonian problem is not an artificial gadget — it is the computational task of quantum chemistry and condensed-matter physics, asking for the ground-state energy of a many-body system. Its $\mathsf{QMA}$ -completeness is a precise statement that, in the worst case, there is no efficient algorithm (quantum or classical) for ground-state energies, unless $\mathsf{BQP} = \mathsf{QMA}$ . This explains at a fundamental level why ab-initio energy calculations are hard, justifies heuristic methods (variational, quantum Monte Carlo, DMRG) as the practical recourse, and motivates the search for physically restricted families (e.g. gapped 1D systems, or stoquastic Hamiltonians, which fall into the class $\mathsf{StoqMA}$ ) where the problem becomes tractable.

Takeaways

Local Hamiltonian is to $\mathsf{QMA}$ what $\mathsf{SAT}$ is to $\mathsf{NP}$ : complete, robust under restriction of locality and geometry, and a bridge between abstract complexity and a real physical computation. Its hardness is the complexity-theoretic reason that simulating quantum matter is, in general, intractable.