129
Part Three · C · Complexity and cryptography

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 H=∑jHjH = \sum_j H_j on nn qubits, each term acting on at most kk qubits, and two thresholds a<ba < b separated by at least 1/poly(n)1/\mathrm{poly}(n), decide whether the ground energy is below aa or above bb. 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 k=5k = 5; Julia Kempe, Kitaev and Oded Regev reduced it to k=2k = 2 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 UT⋯U1U_T\cdots U_1 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 tt is not UtU_t applied to step t−1t-1 (h.c. is the Hermitian conjugate of the term before it, and UtU_t acts on the computation register):

Hprop=12∑t=1Ththt=∣t⟩⟨t∣+∣t−1⟩⟨t−1∣−Ut∣t⟩⟨t−1∣−h.c.\begin{aligned}H_\text{prop} &= \tfrac12\textstyle\sum_{t=1}^{T} h_t\\ h_t &= |t\rangle\langle t| + |t{-}1\rangle\langle t{-}1|\\ &\quad - U_t|t\rangle\langle t{-}1| - \text{h.c.}\end{aligned}

Its zero-energy ground state is the history state 1T+1∑tUt⋯U1∣ψ⟩∣t⟩\frac{1}{\sqrt{T+1}}\sum_t U_t\cdots U_1|\psi\rangle|t\rangle, an equal superposition of every step of the computation. Further terms check the input and penalize a “no” output. With T=T = 3 gates, the plate shows the spectrum of HpropH_\text{prop}, which is a walk on a line of T+1T+1 clock states with eigenvalues 1−cos⁡(πj/(T+1))1-\cos(\pi j/(T+1)). The gap is 1−cos⁡(π/(T+1))≈π2/2T21 - \cos(\pi/(T+1)) \approx \pi^2/2T^2: polynomially small, which is why the promise gap b−ab - a need only be 1/poly1/\mathrm{poly}. 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.

What is the history state?tap
An equal superposition over clock times t of the computation’s state after t gates, tagged by |t⟩.
How does the clock Hamiltonian’s gap scale?tap
As about π²/2T², polynomially small in the number of gates.
Does QMA-hardness doom quantum chemistry?tap
No: it is a worst-case result; physical molecules may be far easier.

And one to work out. What is the gap of HpropH_\text{prop} for a 3-gate circuit?

gap =

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.

Next · Chapter 130
Lower bounds: polynomial and adversary methods

How do you prove no quantum algorithm can do better, including ones nobody has invented yet?

Turn the page