Simple Algorithm
Quantum Computing · Rydberg State · 32 min

QMA & the Local Hamiltonian Problem

The quantum Cook–Levin theorem.

Cook and Levin showed that satisfiability of Boolean formulas captures all of NP. Kitaev proved the quantum analogue: estimating the ground-state energy of a local Hamiltonian captures every problem with an efficiently checkable quantum proof. The bridge between computation and physics is a superposition over the history of a computation.

What you’ll learn

  • Define QMA, QCMA and MA, and explain parallel and in-place (Marriott–Watrous) error reduction.
  • Prove QMA⊆PP\mathsf{QMA}\subseteq\mathsf{PP} using strong error reduction.
  • Show that the kk-local Hamiltonian problem is in QMA.
  • Construct the Feynman–Kitaev history-state Hamiltonian, compute the spectrum of its propagation term, and explain why it is 5-local.
  • Describe the reductions to 2-local and lattice Hamiltonians via perturbative gadgets, and their consequences for physics and chemistry.

Quantum proofs

Immediately, NP⊆MA⊆QCMA⊆QMA\mathsf{NP}\subseteq\mathsf{MA}\subseteq\mathsf{QCMA}\subseteq\mathsf{QMA} and BQP⊆QMA\mathsf{BQP}\subseteq\mathsf{QMA} (ignore the witness). Mixed witnesses never help a cheating prover, because acceptance probability is linear in the density matrix and is maximized at a pure state.

DerivationQMA ⊆ PP (the Marriott–Watrous proof)
  1. Qx:=(⟨0m∣⊗I) Vx† Πacc Vx (∣0m⟩⊗I),max⁡ξPr⁡[accept]=λmax⁡(Qx)Q_x := \big(\bra{0^m}\otimes\id\big)\,V_x^\dagger\,\Pi_{\mathrm{acc}}\,V_x\,\big(\ket{0^m}\otimes\id\big),\qquad \max_\xi\Pr[\text{accept}] = \lambda_{\max}(Q_x)

    The acceptance operator on the 2p2^p-dimensional witness space, with 0⪯Qx⪯I0\preceq Q_x\preceq\id.

  2. r=p+2:x∈Πyes⇒Tr⁡Qx≥λmax⁡≥1−2−(p+2)≥34;x∈Πno⇒Tr⁡Qx≤2pλmax⁡≤14r = p+2:\qquad x\in\Pi_{\mathrm{yes}}\Rightarrow\Tr Q_x\ge\lambda_{\max}\ge1-2^{-(p+2)}\ge\tfrac34;\qquad x\in\Pi_{\mathrm{no}}\Rightarrow\Tr Q_x\le2^p\lambda_{\max}\le\tfrac14

    In-place amplification pushes soundness below 2−p2^{-p} without enlarging the witness, so even the trace, a sum of 2p2^p eigenvalues, stays small.

  3. Tr⁡Qx=2p⋅Pr⁡[Vx accepts the maximally mixed witness I/2p]\Tr Q_x = 2^p\cdot\Pr\big[V_x\text{ accepts the maximally mixed witness }\id/2^p\big]

    A maximally mixed witness is a uniformly random basis string: a quantum computation with no prover at all.

  4. Deciding whether this acceptance probability is ≥34⋅2−p\ge\tfrac34\cdot2^{-p} or ≤14⋅2−p\le\tfrac14\cdot2^{-p} is a threshold question about a GapP quantity, exactly as in the proof of BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP}. Hence QMA⊆PP\mathsf{QMA}\subseteq\mathsf{PP}, a containment first shown by Kitaev and Watrous. ■\blacksquare

The local Hamiltonian problem

Derivationk-local Hamiltonian is in QMA
  1. 0⪯Hj⪯I0\preceq H_j\preceq\id

    Shift and rescale each term (and the thresholds accordingly).

  2. j∈R[m];measure {Hj, I−Hj} on ∣ξ⟩;accept on outcome I−Hjj\in_R[m];\quad\text{measure }\{H_j,\ \id-H_j\}\text{ on }\ket\xi;\quad\text{accept on outcome }\id-H_j

    HjH_j acts on k=O(1)k = \order{1} qubits, so this two-outcome measurement is a small circuit: diagonalize HjH_j, then rotate an ancilla by an eigenvalue-dependent angle.

  3. Pr⁡[accept]=1−1m∑j⟨ξ∣Hj∣ξ⟩=1−⟨ξ∣H∣ξ⟩m\Pr[\text{accept}] = 1-\frac1m\sum_j\bra\xi H_j\ket\xi = 1-\frac{\bra\xi H\ket\xi}{m}

    With a ground state as witness, at least 1−a/m1-a/m in yes-instances; no witness exceeds 1−b/m1-b/m in no-instances.

  4. The gap (b−a)/m≥1/poly⁡(n)(b-a)/m\ge1/\poly(n) is amplified by error reduction. ■\blacksquare

Kitaev's theorem: the Feynman–Kitaev clock

Cook–Levin writes down the whole tableau of a computation and checks each step locally. Quantumly, the intermediate states are entangled nn-qubit states that cannot be copied side by side. Feynman's idea (1985), turned into a proof by Kitaev, is to superpose them instead, labeled by a clock.

∣η⟩=1T+1∑t=0TUt⋯U1∣ξ,0m⟩⊗∣t⟩clock\ket\eta = \frac{1}{\sqrt{T+1}}\sum_{t=0}^{T}U_t\cdots U_1\ket{\xi,0^m}\otimes\ket{t}_{\mathrm{clock}}
The history state of the verifier UT⋯U1U_T\cdots U_1 run on witness ∣ξ⟩\ket\xi.
DerivationThe circuit-to-Hamiltonian construction
  1. H=Hin+Hprop+Hout (+ Hclock)H = H_{\mathrm{in}} + H_{\mathrm{prop}} + H_{\mathrm{out}}\ \big(+\,H_{\mathrm{clock}}\big)

    Each term penalizes one kind of inconsistency with an accepting history.

  2. Hin=∑i∈anc∣1⟩ ⁣⟨1∣i⊗∣0⟩ ⁣⟨0∣clock,Hout=∣0⟩ ⁣⟨0∣out⊗∣T⟩ ⁣⟨T∣clockH_{\mathrm{in}} = \sum_{i\in\mathrm{anc}}\dyad{1}_i\otimes\dyad{0}_{\mathrm{clock}},\qquad H_{\mathrm{out}} = \dyad{0}_{\mathrm{out}}\otimes\dyad{T}_{\mathrm{clock}}

    At time 00 the ancillas must be ∣0⟩\ket0; at time TT the output qubit should read 11.

  3. Hprop=∑t=1T12(I⊗∣t⟩ ⁣⟨t∣+I⊗∣t−1⟩ ⁣⟨t−1∣−Ut⊗∣t⟩ ⁣⟨t−1∣−Ut†⊗∣t−1⟩ ⁣⟨t∣)H_{\mathrm{prop}} = \sum_{t=1}^{T}\tfrac12\Big(\id\otimes\dyad{t}+\id\otimes\dyad{t-1}-U_t\otimes\ketbra{t}{t-1}-U_t^\dagger\otimes\ketbra{t-1}{t}\Big)

    Penalizes any mismatch between the state at time tt and UtU_t applied to the state at time t−1t-1.

  4. W:=∑tUt⋯U1⊗∣t⟩ ⁣⟨t∣:W†HpropW=I⊗12∑t=1T(∣t⟩−∣t−1⟩)(⟨t∣−⟨t−1∣)\mathcal{W} := \sum_tU_t\cdots U_1\otimes\dyad{t}:\qquad\mathcal{W}^\dagger H_{\mathrm{prop}}\mathcal{W} = \id\otimes\tfrac12\sum_{t=1}^{T}\big(\ket{t}-\ket{t-1}\big)\big(\bra{t}-\bra{t-1}\big)

    In the frame of the computation the gates disappear: what remains is half the Laplacian of a path graph on the T+1T+1 clock states.

  5. spec⁡(Hprop)={1−cos⁡πkT+1: k=0,…,T},gap=1−cos⁡πT+1≈π22(T+1)2\operatorname{spec}(H_{\mathrm{prop}}) = \Big\{1-\cos\tfrac{\pi k}{T+1}:\ k = 0,\dots,T\Big\},\qquad\text{gap} = 1-\cos\tfrac{\pi}{T+1}\approx\frac{\pi^2}{2(T+1)^2}

    The null space consists of history states, one for each witness; the spectral gap is Θ(1/T2)\Theta(1/T^2).

  6. yes: ⟨η∣H∣η⟩=1−Pr⁡[accept]T+1≤εT+1;no: λmin⁡(H)≥c 1−εT3\text{yes: }\bra\eta H\ket\eta = \frac{1-\Pr[\text{accept}]}{T+1}\le\frac{\varepsilon}{T+1};\qquad\text{no: }\lambda_{\min}(H)\ge c\,\frac{1-\sqrt\varepsilon}{T^3}

    In yes-instances only HoutH_{\mathrm{out}} contributes. In no-instances (every witness accepted with probability ≤ε\le\varepsilon), Kitaev's geometric lemma gives the lower bound for a constant cc. After amplification, the promise gap is 1/poly⁡1/\poly.

Predict before you look

Encode the clock in unary, ∣t⟩↦∣1t0T−t⟩\ket{t}\mapsto\ket{1^t0^{T-t}} on TT clock qubits, and use two-qubit gates UtU_t. On how many qubits does one propagation term act (for 1<t<T1<t<T)?

Show the answer

5 qubits

∣t⟩ ⁣⟨t−1∣\ketbra{t}{t-1} only needs to check clock qubits t−1t-1 and t+1t+1 and flip qubit tt: it is ∣110⟩ ⁣⟨100∣\ketbra{110}{100} on clock qubits (t−1,t,t+1)(t-1,t,t+1). With the two qubits of UtU_t that makes 5. Illegal clock strings are penalized by the 2-local Hclock=∑i∣01⟩ ⁣⟨01∣i,i+1H_{\mathrm{clock}} = \sum_i\dyad{01}_{i,i+1}, and HinH_{\mathrm{in}}, HoutH_{\mathrm{out}} are 2-local. Hence "5-local".

Down to two-local, and what it means

ResultSettingReference
QMA-complete5-localKitaev 1999; Kitaev, Shen & Vyalyi 2002
QMA-complete3-localKempe & Regev 2003
QMA-complete2-local qubit HamiltoniansKempe, Kitaev & Regev 2006
QMA-complete2-local, qubits on a 2D square latticeOliveira & Terhal 2008
QMA-completenearest-neighbor chain of constant-dimensional quditsAharonov, Gottesman, Irani & Kempe 2009
P, NP-, StoqMA- or QMA-completeclassification of 2-local qubit interaction typesCubitt & Montanaro 2016
in NPcommuting 2-local HamiltoniansBravyi & Vyalyi 2005
in Pground states of gapped 1D HamiltoniansLandau, Vazirani & Vidick 2015
DerivationPerturbative gadgets: trading locality for energy scales
  1. H~=Δ ∣1⟩ ⁣⟨1∣m+V,V=Δ2 (B−A)⊗Xm\tilde H = \Delta\,\dyad{1}_{\mathrm{m}} + V,\qquad V = \sqrt{\tfrac{\Delta}{2}}\,(B-A)\otimes X_{\mathrm{m}}

    A mediator qubit m\mathrm{m} pays energy Δ\Delta for being in ∣1⟩\ket1. AA and BB act on disjoint sets of qubits, so [A,B]=0\comm{A}{B} = 0, and each coupling is only one qubit more local than AA or BB.

  2. Heff=Π−VΠ−−1Δ Π−V Π+ V Π−+O(∥V∥3Δ2)H_{\mathrm{eff}} = \Pi_-V\Pi_- - \frac1\Delta\,\Pi_-V\,\Pi_+\,V\,\Pi_- + \order{\frac{\norm{V}^3}{\Delta^2}}

    Second-order perturbation theory (Schrieffer–Wolff) in the low-energy subspace Π−=∣0⟩ ⁣⟨0∣m\Pi_- = \dyad{0}_{\mathrm{m}}. The first-order term vanishes because XmX_{\mathrm{m}} flips the mediator.

  3. Heff=−12(B−A)2+O(Δ−1/2)=AB−12(A2+B2)+O(Δ−1/2)H_{\mathrm{eff}} = -\tfrac12(B-A)^2 + \order{\Delta^{-1/2}} = AB - \tfrac12\big(A^2+B^2\big) + \order{\Delta^{-1/2}}

    The product ABAB acts on the union of the two supports: a higher-locality interaction emerges from lower-locality couplings. The A2A^2, B2B^2 terms are less local and can be compensated. Iterating such subdivision gadgets, with a third-order gadget for 3-body terms, reduces 5-local to 2-local at the price of polynomially large Δ\Delta.

Two consequences:

  • Nature does not always cool efficiently. A physical system that always relaxed quickly to its ground state would solve QMA-hard problems. Frustrated systems and spin glasses get stuck instead.
  • Quantum chemistry needs good initial states. Phase estimation finds a ground energy efficiently only when given a trial state with non-negligible overlap with the ground state. With such a guiding state, ground-energy estimation to inverse-polynomial precision becomes BQP-complete (Gharibian & Le Gall 2022). The hardness lives in finding the state.
Check your understanding

Which local Hamiltonian problem is not believed to be QMA-complete?

  1. 2-local qubit Hamiltonians on a 2D square lattice
  2. 3-local qubit Hamiltonians
  3. Commuting 2-local Hamiltonians
  4. Nearest-neighbor Hamiltonians on a chain of constant-dimensional qudits
Show the answer

C. Commuting 2-local Hamiltonians

Bravyi and Vyalyi showed that the commuting 2-local Hamiltonian problem is in NP: the structure of commuting terms lets a classical certificate describe a ground state. If it were QMA-complete, QMA would collapse to NP.

Key takeaways

  • QMA = efficiently verifiable quantum proofs; NP⊆MA⊆QCMA⊆QMA⊆PP\mathsf{NP}\subseteq\mathsf{MA}\subseteq\mathsf{QCMA}\subseteq\mathsf{QMA}\subseteq\mathsf{PP}, the last via in-place amplification and a trace argument.
  • The kk-local Hamiltonian problem with an inverse-polynomial promise gap is in QMA: measure a random term on the claimed ground state.
  • Kitaev's history-state Hamiltonian makes QMA verification a ground-energy question; HpropH_{\mathrm{prop}} is a path Laplacian with gap Θ(1/T2)\Theta(1/T^2), and a unary clock makes it 5-local.
  • Perturbative gadgets reduce hardness to 2-local qubit, 2D lattice and even 1D qudit Hamiltonians.
  • Worst-case ground-state problems are hard even for quantum computers; quantum chemistry speedups hinge on good initial states.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why does the Feynman–Kitaev construction superpose the computation over a clock instead of writing out every intermediate state, as the Cook–Levin tableau does?

  1. To make the Hamiltonian stoquastic
  2. Intermediate states are entangled nn-qubit states that cannot be copied into a tableau; superposing them over a clock turns "step tt follows from step t−1t-1" into a local hopping term
  3. A clock register uses fewer qubits than the witness
  4. Measuring intermediate states would collapse the witness
Show the answer

B. Intermediate states are entangled nn-qubit states that cannot be copied into a tableau; superposing them over a clock turns "step tt follows from step t−1t-1" into a local hopping term

In the history state, HpropH_{\mathrm{prop}} compares consecutive time slices coherently with terms like Ut⊗∣t⟩ ⁣⟨t−1∣U_t\otimes\ketbra{t}{t-1}, which are local once the clock is unary.

Question 2

Why must the promise gap b−ab-a be at least inverse-polynomial?

  1. Otherwise the problem would not be in NP
  2. Otherwise 1-local Hamiltonians would suffice
  3. Kitaev's construction produces exponentially large gaps
  4. The verifier's acceptance gap is (b−a)/m(b-a)/m and must be amplified with polynomially many repetitions; with exponentially small gaps the problem becomes PSPACE-complete
Show the answer

D. The verifier's acceptance gap is (b−a)/m(b-a)/m and must be amplified with polynomially many repetitions; with exponentially small gaps the problem becomes PSPACE-complete

Bounded-error verification needs an inverse-polynomial gap to amplify. Precise (exponentially small gap) local-Hamiltonian estimation is PSPACE-complete.

Question 3

How does the spectral gap of HpropH_{\mathrm{prop}} scale with the number of gates TT?

  1. Θ(1/T2)\Theta(1/T^2)
  2. Θ(1/T)\Theta(1/T)
  3. Θ(1)\Theta(1)
  4. Θ(2−T)\Theta(2^{-T})
Show the answer

A. Θ(1/T2)\Theta(1/T^2)

HpropH_{\mathrm{prop}} is unitarily equivalent to half the Laplacian of a path on T+1T+1 vertices, with gap 1−cos⁡πT+1≈π22(T+1)21-\cos\frac{\pi}{T+1}\approx\frac{\pi^2}{2(T+1)^2}.

Question 4

In the proof of QMA⊆PP\mathsf{QMA}\subseteq\mathsf{PP}, why is in-place (Marriott–Watrous) amplification used rather than parallel repetition?

  1. Parallel repetition is unsound against entangled witnesses
  2. PP machines cannot repeat computations
  3. Parallel repetition multiplies the witness length, so the soundness error never drops below the inverse dimension; in-place amplification keeps pp fixed while r=p+2r = p+2
  4. It is not needed: plain QMA soundness 1/31/3 already gives Tr⁡Qx≤1/4\Tr Q_x\le1/4
Show the answer

C. Parallel repetition multiplies the witness length, so the soundness error never drops below the inverse dimension; in-place amplification keeps pp fixed while r=p+2r = p+2

The argument needs soundness smaller than 2−p2^{-p} so that Tr⁡Qx≤2pλmax⁡\Tr Q_x\le2^p\lambda_{\max} stays small. With kk copies, the witness space has dimension 2kp2^{kp} while soundness only falls like 2−Ω(k)2^{-\Omega(k)}, so the trace bound never improves.

Further reading

  • A. Yu. Kitaev, A. H. Shen & M. N. Vyalyi, Classical and Quantum Computation, Ch. 14 (AMS, 2002).
  • J. Kempe, A. Kitaev & O. Regev, "The complexity of the local Hamiltonian problem", SIAM Journal on Computing 35, 1070 (2006).
  • C. Marriott & J. Watrous, "Quantum Arthur–Merlin games", Computational Complexity 14, 122 (2005).
  • S. Gharibian, Y. Huang, Z. Landau & S. W. Shin, "Quantum Hamiltonian complexity", Foundations and Trends in Theoretical Computer Science 10, 159 (2015).
  • R. P. Feynman, "Quantum mechanical computers", Optics News 11, 11 (1985).