QMA-completeness and the local Hamiltonian problem
Finding the ground-state energy of a molecule or a material is the central problem of quantum chemistry and condensed-matter physics, and the most promising use of quantum computers. Yet in 1999 Alexei Kitaev proved that a version of this problem is as hard as anything a quantum computer can verify: QMA-complete. In the worst case, even a quantum computer is not expected to find ground energies efficiently. Understanding why, and why it does not doom chemistry, tells you a lot about what hardness means.
On the plate: a Hamiltonian whose ground state is the entire history of a computation.
The local Hamiltonian problem
Given on qubits, each term acting on at most qubits, and two thresholds separated by at least , decide whether the ground energy is below or above . It is in QMA: the witness is the ground state itself, and the verifier estimates its energy with phase estimation. Kitaev proved it is QMA-hard for ; Julia Kempe, Kitaev and Oded Regev reduced it to in 2006 using perturbation-theory “gadgets”, and later work brought it down to 2-local Hamiltonians on a 2D lattice. Established
The Feynman–Kitaev clock
To encode a circuit in a Hamiltonian, Kitaev borrowed an idea of Feynman’s: add a clock register, and define a propagation term that penalizes any state where step is not applied to step (h.c. is the Hermitian conjugate of the term before it, and acts on the computation register):
Its zero-energy ground state is the history state , an equal superposition of every step of the computation. Further terms check the input and penalize a “no” output. With 3 gates, the plate shows the spectrum of , which is a walk on a line of clock states with eigenvalues . The gap is : polynomially small, which is why the promise gap need only be . Established
What it means for chemistry, and quantum PCP
Norbert Schuch and Frank Verstraete showed in 2009 that computing the exact universal functional of density functional theory is QMA-hard. These are worst-case statements about specially constructed Hamiltonians. Real molecules may be easier: nature finds their ground states by cooling, and good approximate starting states exist for most of chemistry (Part 5). The real question is whether quantum computers help for the molecules we care about, not in the worst case. Debated
A deeper open problem is the quantum PCP conjecture: is it still QMA-hard to estimate the energy to within a constant fraction of the number of terms? A necessary step, the NLTS conjecture (no low-energy trivial states), asserting Hamiltonians whose every low-energy state needs deep circuits, was proved by Anurag Anshu, Nikolas Breuckmann and Chinmay Nirkhe in 2023 using good quantum LDPC codes (Chapter 141). Quantum PCP itself remains open. Debated
What you now have
The local Hamiltonian problem, its membership in QMA, the Feynman–Kitaev clock construction and its gap, reductions to 2-local, the meaning of worst-case hardness for chemistry, and the status of NLTS and quantum PCP.
· · ·
Three questions to carry with you.
And one to work out. What is the gap of for a 3-gate circuit?
Sources: A. Kitaev, A. Shen and M. Vyalyi, Classical and Quantum Computation (AMS, 2002), ch. 14. J. Kempe, A. Kitaev and O. Regev, SIAM J. Comput. 35, 1070 (2006). N. Schuch and F. Verstraete, Nat. Phys. 5, 732 (2009). S. Gharibian, Y. Huang, Z. Landau and S. W. Shin, Found. Trends Theor. Comput. Sci. 10, 159 (2015). A. Anshu, N. P. Breuckmann and C. Nirkhe, Proc. 55th ACM STOC, 1090 (2023). Checked by code: gaps 1, 0.5, 0.293, 0.191 for T = 1–4; exact diagonalization agrees.