TY - JOUR

T1 - The complexity of the local Hamiltonian problem

AU - Kempe, Julia

AU - Kitaev, Alexei

AU - Regev, Oded

PY - 2004

Y1 - 2004

N2 - 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 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. The second proof uses elementary linear algebra only. Using our techniques we also show that adiabatic computation with two-local interactions on qubits is equivalent to standard quantum computation.

AB - 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 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. The second proof uses elementary linear algebra only. Using our techniques we also show that adiabatic computation with two-local interactions on qubits is equivalent to standard quantum computation.

UR - http://www.scopus.com/inward/record.url?scp=34147163913&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34147163913&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30538-5_31

DO - 10.1007/978-3-540-30538-5_31

M3 - Article

AN - SCOPUS:34147163913

SN - 0302-9743

VL - 3328

SP - 372

EP - 383

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -