The complexity of the local hamiltonian problem

Julia Kempe, Alexei Kitaev, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

The k-LOCAL HAMILTONIAN problem is & natural complete problem for the complexity class QMA, the quantum analogue 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 2-local interactions on qubits is equivalent to standard quantum computation.

Original languageEnglish (US)
Pages (from-to)1070-1097
Number of pages28
JournalSIAM Journal on Computing
Volume35
Issue number5
DOIs
StatePublished - 2006

Keywords

  • Adiabatic computation
  • Complete problems
  • Local Hamiltonian problem
  • Quantum computation

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The complexity of the local hamiltonian problem'. Together they form a unique fingerprint.

Cite this