The Complexity of the Local Hamiltonian Problem

The k-{} problem is a natural complete problem for the complexity class , the quantum analogue of . It is similar in spirit to { MAX-k-SAT}, which is -complete for k≥ 2. It was known that the problem is -complete for any k ≥ 3. On the other hand, 1-{} is in {} and hence not believed to be -complete. The complexity of the 2-{} problem has long been outstanding. Here we settle the question and show that it is -complete. We provide two independent proofs; our first proof uses only elementary linear algebra. Our second proof uses a powerful technique for analyzing the sum of two Hamiltonians; this technique is based on perturbation theory and we believe that it might prove useful elsewhere. Using our techniques we also show that adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation.