QMA-completeness of the 2-local Hamiltonian problem

Short answer: The local Hamiltonian problem is the natural complete problem for QMA, the quantum analogue of NP. A paper in the SIAM Journal on Computing settles the long-standing open case of two-body interactions by proving that the 2-local version is QMA-complete, with two independent proofs. The same techniques show that adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation. This is complexity theory, and says nothing about whether any device can solve these problems.

The problem

The k-local Hamiltonian problem is described in the paper's abstract as similar in spirit to MAX-k-SAT. It asks about the smallest eigenvalue of a sum of local terms, each acting on k qubits: is it below a threshold a or above a threshold b, where the gap b minus a is at least 1 over a polynomial in the number of qubits. A survey of Kitaev's 1999 result describes how he defined the class QMA, the quantum analogue of NP, and showed that a natural extension of 3-SAT, local Hamiltonians, is QMA-complete. The survey says the proof builds on the classical Cook-Levin proof of NP-completeness of SAT but differs from it in several fundamental ways.

Where the two-local case sat

The SIAM paper says the problem was known to be QMA-complete for any k of 3 or more. It notes that the 1-local problem is in P and so is not believed to be QMA-complete. The complexity of the 2-local problem, the authors say, had long been outstanding.

The result

The authors settle the question and show that the 2-local Hamiltonian problem is QMA-complete. They give two independent proofs. The first uses only elementary linear algebra. The second uses a technique for analysing the sum of two Hamiltonians based on perturbation theory, which they believe might prove useful elsewhere.

Adiabatic computation

Using their techniques, the authors also show that adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation. In other words, in their analysis restricting to pairwise interactions does not reduce the power of the adiabatic model.

What it does not say

QMA-completeness is a statement about worst-case hardness: finding whether a ground-state energy is low is as hard as any problem in QMA, which is believed to be hard even for quantum computers. It does not say that every physical Hamiltonian is hard, and it does not describe any hardware.

FAQ

What is QMA?

The quantum analogue of NP, according to the papers cited.

What did the paper prove?

That the 2-local Hamiltonian problem is QMA-complete.

Why was the two-local case open?

The authors say the case k=3 and above was known to be QMA-complete, and k=1 is in P, so k=2 had long been outstanding.

How was it proved?

Two independent proofs: one with elementary linear algebra, one using perturbation theory.

What is the link to adiabatic computation?

Adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation, per the same paper.