The Local Hamiltonian Problem

The Local Hamiltonian problem is the reference point of a living research program. In quantum chemistry, molecular electronic-structure Hamiltonians become local Hamiltonians after Jordan–Wigner or Bravyi–Kitaev mappings, and the QMA-completeness of LH is the formal reason that exact ground-state energy estimation is believed hard even for a quantum computer in the worst case — which is why practitioners reach for heuristics like the variational quantum eigensolver rather than a universal algorithm. In complexity theory LH calibrates the whole QMA landscape: constrain the terms and you carve out StoqMA (sign-problem-free), QMA$_1$ (perfect completeness), and the commuting-Hamiltonian corner that flirts with NP. The frontier is the quantum PCP conjecture, which asks whether LH stays QMA-hard even with a constant relative promise gap; a landmark step came in 2022 when Anshu, Breuckmann, and Nirkhe proved the No Low-energy Trivial States (NLTS) theorem — that certain local Hamiltonians have no low-energy states expressible by shallow circuits — supplying a necessary condition for quantum PCP. And because BQP embeds into LH ground states through universal adiabatic computation, the problem also underwrites quantum annealing and the ground-state model of computation.

Picture the problem as MAX-$k$-SAT promoted to the quantum world. A SAT formula is a list of clauses over bits, satisfiable exactly when the minimum number of violated clauses is zero. A local Hamiltonian is a list of energy penalties over qubits, and its ground energy is the minimum total violation — except now the assignment is a quantum state and the clauses are Hermitian operators. The rules change decisively in one way: the optimal state can be globally entangled, so you cannot read off the answer one constraint at a time. That is the whole reason the problem escapes NP and lands in QMA. The first figure fixes the objects. A handful of qubits sit under a scatter of local terms, each term penalizing its own little cluster; the ground energy is the least total penalty summed over every state, and the decision problem only asks on which side of a promise gap that number falls.

The conceptual heart of the whole subject is the history state. To force a static energy landscape to certify a dynamic computation, Kitaev appends a clock register and writes a Hamiltonian that penalizes any configuration that is not a faithful snapshot sequence of a verifier circuit running. The unique zero-energy state is then compelled to be a uniform superposition over every time step of the computation, $|\eta\rangle\propto\sum_t|\psi_t\rangle|t\rangle$, with the energy low precisely when the propagation is consistent and the final snapshot is accepting. On the clock line the propagation term becomes the Laplacian of a path graph, and its tiny but nonzero spectral gap is the machine that manufactures the inverse-polynomial promise gap of QMA. The second figure carries the real number: for a modest circuit of $T=10$ gates the path-graph gap is $1-\cos(\pi/11)=0.0405$.

Two structural facts complete the picture. First, why an inverse-polynomial gap and not a constant one? The propagation Hamiltonian is a quantum walk on a line of $T+1$ vertices, whose smallest nonzero Laplacian eigenvalue is $\Theta(1/T^2)$; after the bookkeeping that couples this gap to the output penalty, the guaranteed YES/NO separation is only inverse-polynomial — precisely QMA's completeness/soundness margin. Second, locality trades against geometry and arity. Kitaev's construction is $5$-local; perturbation gadgets squeeze it to $2$-local, and clever encodings force it onto a 2D lattice and even a 1D chain of constant-dimension qudits. That the hardness survives every such restriction shows it is intrinsic to quantum mechanics, not an artifact of long-range or high-arity coupling.

A $k$-local Hamiltonian is defined by how narrowly each of its terms reaches. Every term is Hermitian, acts as the identity on all but at most $k$ qubits, and has bounded norm, so the whole operator is specified by polynomially much classical data even though it lives on a $2^n$-dimensional space.

where: $H$ — total Hamiltonian on $n$ qubits, a $2^n\times 2^n$ Hermitian operator; $H_j$ — the $j$-th local term, Hermitian with $\|H_j\|\le\mathrm{poly}(n)$; $\tilde H_j$ — its nontrivial part; $S_j$ — the set of qubits term $j$ acts on; $k$ — locality, the maximum arity $\max_j|S_j|$; $m$ — number of terms, $m=\mathrm{poly}(n)$. Reading: $H$ is a bounded sum of narrow constraints, not a generic exponential-size matrix. The decision problem is a promise problem: the two thresholds are separated by a gap that must be at least inverse-polynomial, and instances are guaranteed to fall on one side or the other, never inside the gap.

where: $\lambda_{\min}(H)$ — the smallest eigenvalue, i.e. the ground-state energy; $a,b$ — thresholds supplied in the input with $a<b$; $b-a$ — the promise gap, required to be at least $1/\mathrm{poly}(n)$. Reading: we never need the exact ground energy, only which side of a comfortably wide gap it lies on. The ground energy has a variational meaning that makes the constraint-satisfaction analogy exact: it is the minimum expected energy over all normalized states, and by linearity that is the sum of the expected costs of the individual constraints.

where: $|\psi\rangle$ — a normalized $n$-qubit state, the variational "assignment"; $\langle\psi|H_j|\psi\rangle$ — the expected cost of constraint $j$ in that assignment. Reading: minimizing energy is minimizing total constraint violation, but over the full space of (possibly entangled) quantum states. The hardness reduction rests on the Feynman–Kitaev history state, which packages an entire run of a verifier circuit $V=U_T\cdots U_1$ into one static superposition indexed by a clock.

where: $U_t$ — the $t$-th gate; $|\xi\rangle$ — the input register (witness qubits together with ancillas set to $|0\rangle$); $|t\rangle$ — the clock state for time $t$ (unary in Kitaev's construction); $T=\mathrm{poly}(n)$ — the circuit length. Reading: the ground state is not a single snapshot but an equal-weight superposition over all $T+1$ snapshots of the computation. The clock Hamiltonian is a sum of four penalty groups, one enforcing correct input, one enforcing correct propagation, one forbidding illegal clock states, and one penalizing a rejecting output. The propagation group is the interesting one: it is a sum of small projectors, each annihilated exactly by a correctly propagated pair of consecutive snapshots.

where: the diagonal pieces charge one unit of energy to the two clock times $t{-}1,t$; the off-diagonal $U_t\otimes|t\rangle\langle t{-}1|$ links consecutive snapshots and costs zero energy exactly when $|\psi_t\rangle=U_t|\psi_{t-1}\rangle$. Reading: each term is a projector whose kernel is the correctly propagated history, so the whole history state sits at zero propagation energy. Finally, acceptance is read out of the output penalty, which lives only on the last time slice. Its expectation in the history state converts the verifier's acceptance probability directly into an energy.

where: $H_{\mathrm{out}}=(|0\rangle\langle0|)_{\mathrm{out}}\otimes|T\rangle\langle T|$ penalizes a rejecting output qubit at $t=T$; $p_{\mathrm{acc}}$ — the probability the verifier accepts; the prefactor $1/(T+1)$ is the clock amplitude weight. Reading: an almost-always-accepting witness gives an almost-zero output energy, so YES instances have low ground energy and NO instances do not.

How the complexity moves as the Hamiltonian family is restricted or loosened:

1 · Why a two-local term already forces entanglement (fully worked)

Take the single antiferromagnetic Heisenberg term $H=\tfrac14(X\otimes X+Y\otimes Y+Z\otimes Z)$ on two qubits. Find its ground energy and ground state, and compare against the best product (unentangled) state. This is the smallest instance that shows why LH is not classical MAX-SAT.

Step 1. Diagonalize in the basis $\{|00\rangle,|01\rangle,|10\rangle,|11\rangle\}$. The operator $\sigma\!\cdot\!\sigma=X\otimes X+Y\otimes Y+Z\otimes Z$ leaves $|00\rangle$ and $|11\rangle$ at energy $+1$ (the $ZZ$ diagonal, with the off-diagonal $XX,YY$ pieces cancelling on that pair), and mixes $|01\rangle,|10\rangle$ through the block $\begin{pmatrix}-1&2\\2&-1\end{pmatrix}$ with eigenvalues $-1\pm2$. So $\sigma\!\cdot\!\sigma$ has eigenvalues $\{+1,+1,+1,-3\}$.

Step 2. Scale by $\tfrac14$: the eigenvalues of $H$ are $\{+\tfrac14,+\tfrac14,+\tfrac14,-\tfrac34\}$, so the ground energy is $\boldsymbol{\lambda_{\min}=-\tfrac34}$. The $-3$ eigenvalue belongs to the spin singlet $|\Psi^-\rangle=(|01\rangle-|10\rangle)/\sqrt2$, which is maximally entangled — it has no product-state form at all.

Step 3. Now restrict to product states $|a\rangle\otimes|b\rangle$. Then $\langle\sigma\!\cdot\!\sigma\rangle=\langle X\rangle_a\langle X\rangle_b+\langle Y\rangle_a\langle Y\rangle_b+\langle Z\rangle_a\langle Z\rangle_b=\vec n_a\!\cdot\!\vec n_b$, a dot product of two Bloch unit vectors, minimized at $-1$ when the spins point antiparallel. So the best product energy is $\tfrac14(-1)=\boldsymbol{-\tfrac14}$.

Step 4. Compare: the true ground energy $-\tfrac34$ is strictly below the best product energy $-\tfrac14$, a shortfall of $\tfrac12$. No unentangled assignment reaches the optimum. This is the whole story of LH versus classical CSP in one term — a $1$-local Hamiltonian would be minimized by a product state, but this $2$-local term is frustrated onto an entangled ground state, which is the seed of QMA-hardness. λ_min = −3/4 (entangled singlet); best product state only reaches −1/4.

2 · The promise gap of a ten-gate verifier (fully worked)

A QMA verifier runs $T=10$ gates. Using the history-state construction, find the YES threshold $a$, the propagation spectral gap, and the energy precision Arthur must achieve.

Step 1. The clock has $T+1=11$ time steps, and a $p_{\mathrm{acc}}=2/3$ accepting witness gives history-state energy $\langle\eta|H|\eta\rangle=(1-\tfrac23)/11=\tfrac{1}{33}$, so $\boldsymbol{a=1/33\approx0.0303}$.

Step 2. On the legal subspace the propagation gap is $1-\cos\frac{\pi}{T+1}=1-\cos\frac{\pi}{11}=\boldsymbol{0.0405}$, in agreement with the small-angle estimate $\pi^2/2(11)^2=0.0408$. This is the energy any deviation from a valid history must pay.

Step 3. Kitaev's geometric lemma turns these into a promise gap $b-a=\Omega(1/T^3)$; with $T=10$ that is of order $10^{-3}$, so $b$ sits a few thousandths above $a$. Arthur must estimate energy to precision better than $(b-a)/2\sim5\times10^{-4}$.

Step 4. By Chernoff, resolving an energy to precision $\varepsilon$ with the bounded local terms needs $O(1/\varepsilon^2)=O(T^6)$ measurement samples — polynomial in $T$, hence polynomial in $n$. The inverse-polynomial gap is exactly what keeps the verification efficient. a = 1/33 ≈ 0.030, propagation gap 0.0405, required precision ~5×10⁻⁴, samples poly(n).

3 · A one-local Hamiltonian is trivially easy

Let $H=\sum_{i=1}^{n}h_i$ with each $h_i$ a single-qubit operator on qubit $i$. Find its ground energy.

Step 1. The terms act on disjoint qubits, so they commute and can be minimized independently. The joint ground state is the product $|\psi^*\rangle=\bigotimes_i|\phi_i\rangle$ where $h_i|\phi_i\rangle=\lambda_{\min}(h_i)|\phi_i\rangle$.

Step 2. Hence $\lambda_{\min}(H)=\sum_{i=1}^{n}\lambda_{\min}(h_i)$, and each $\lambda_{\min}(h_i)$ is the smaller eigenvalue of a $2\times2$ matrix, computable in constant time. Total cost $O(n)$, so $1$-LH $\in$ P. The contrast with Example 1 pinpoints where hardness begins: it is overlap and non-commutation of terms, not locality alone, that manufactures difficulty.

The Local Hamiltonian problem has a clear intellectual owner. The class QMA, the history-state technique, and the completeness theorem all trace to one person, whose reach runs from complexity theory through topological phases of matter to black-hole physics.

Texts. Kitaev, Shen, Vyalyi, Classical and Quantum Computation (2002), Ch. 14 — the original $5$-LH QMA-completeness proof and the history-state machinery · Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniv.), Ch. 2 (spectral theorem) and Ch. 4 (phase estimation) · Watrous, The Theory of Quantum Information (2018) and the survey "Quantum Computational Complexity" (2009) · Kempe, Kitaev, Regev, "The Complexity of the Local Hamiltonian Problem", SIAM J. Comput. 35(5):1070 (2006) — the $2$-local reduction · Aharonov, Gottesman, Irani, Kempe, "The Power of Quantum Systems on a Line", Comm. Math. Phys. 287:41 (2009) — 1D hardness · Gharibian et al., "Quantum Hamiltonian Complexity" (2015) survey · Preskill, Quantum Computation lecture notes (Ph219/CS219). The key checkpoints in this article are: the Rayleigh–Ritz identity $\min_\psi\langle\psi|H|\psi\rangle=\lambda_{\min}$; the path-Laplacian spectrum $1-\cos(\pi r/(T+1))$ with gap $\Theta(1/T^2)$, numerically $0.0405$ at $T=10$; the two-qubit Heisenberg spectrum $\{-3/4,+1/4,+1/4,+1/4\}$ with entangled singlet ground state and best product energy $-1/4$; the QMA membership argument via local-term sampling and Chernoff bounds; and the completeness statements at $k=5$, $k=2$, and 1D. All quoted constants — the $2/3$–$1/3$ QMA gap, $a=1/(3(T+1))$, the $1-\cos$ Laplacian spectrum, the $\Omega(1/T^3)$ promise gap — are standard; gadget-dependent prefactors are flagged as such.

Prerequisites. Quantum Merlin–Arthur (QMA) · The Complexity Class BQP · BQP versus P, NP, and PSPACE. Leads to. The Quantum Cook–Levin Theorem · QMA Variants and Related Classes · QIP = PSPACE.

Ask the tutor: Ask me to walk through Kitaev's history-state construction line by line, or to show exactly why the two-qubit Heisenberg ground state must be entangled.