The Complexity of the Local Hamiltonian Problem
<|reference_start|>The Complexity of the Local Hamiltonian Problem: The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k<=2. It was known that the problem is QMA-complete for any k <= 3. On the other hand 1-local Hamiltonian is in P, and hence not believed to be QMA-complete. The complexity of the 2-local Hamiltonian problem has long been outstanding. Here we settle the question and show that it is QMA-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 two-local interactions on qubits is equivalent to standard quantum computation.<|reference_end|>
@article{kempe2004the,
    title={The Complexity of the Local Hamiltonian Problem},
    author={Julia Kempe, Alexei Kitaev and Oded Regev},
    journal={SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006),
  conference version in Proc. 24th FSTTCS, p. 372-383 (2004)},
    year={2004},
    archivePrefix={arXiv},
    eprint={quant-ph/0406180},
    primaryClass={quant-ph cs.CC}
}