The complexity of the local Hamiltonian problem

Julia Kempe; Alexei Kitaev; Oded Regev

doi:10.1007/978-3-540-30538-5_31

The complexity of the local Hamiltonian problem

Julia Kempe, Alexei Kitaev, Oded Regev

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	372-383
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3328
DOIs	https://doi.org/10.1007/978-3-540-30538-5_31
State	Published - 2004

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

@article{4c5c3bb7ef034b0d924aefe060caada1,

title = "The complexity of the local Hamiltonian problem",

abstract = "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.",

author = "Julia Kempe and Alexei Kitaev and Oded Regev",

note = "Funding Information: Discussions with Sergey Bravyi and Frank Verstraete are gratefully acknowledged. JK is supported by ACI S{\'e}curit{\'e}Informatique, 2003-n24, projet “R{\'e}seaux Quantiques”, ACI-CR 2002-40 and EU 5th framework program RESQ IST-2001-37559, and by DARPA and Air Force Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-01-2-0524, and by DARPA and the Office of Naval Research under grant number FDN-00014-01-1-0826 and during a visit supported in part by the National Science Foundation under grant EIA-0086038 through the Institute for Quantum Information at the California Institute of Technology. AK is supported in part by the National Science Foundation under grant EIA-0086038. OR is supported by an Alon Fellowship and the Army Research Office grant DAAD19-03-1-0082. Part of this work was carried out during a visit of OR at LRI, Universit{\'e}de Paris-Sud and he thanks his hosts for their hospitality and acknowledges partial support by ACI S{\'e}curit{\'e} Informatique, 2003-n24, projet “R{\'e}seaux Quantiques”.",

year = "2004",

doi = "10.1007/978-3-540-30538-5_31",

language = "English (US)",

volume = "3328",

pages = "372--383",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - The complexity of the local Hamiltonian problem

AU - Kempe, Julia

AU - Kitaev, Alexei

AU - Regev, Oded

N1 - Funding Information: Discussions with Sergey Bravyi and Frank Verstraete are gratefully acknowledged. JK is supported by ACI SécuritéInformatique, 2003-n24, projet “Réseaux Quantiques”, ACI-CR 2002-40 and EU 5th framework program RESQ IST-2001-37559, and by DARPA and Air Force Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-01-2-0524, and by DARPA and the Office of Naval Research under grant number FDN-00014-01-1-0826 and during a visit supported in part by the National Science Foundation under grant EIA-0086038 through the Institute for Quantum Information at the California Institute of Technology. AK is supported in part by the National Science Foundation under grant EIA-0086038. OR is supported by an Alon Fellowship and the Army Research Office grant DAAD19-03-1-0082. Part of this work was carried out during a visit of OR at LRI, Universitéde Paris-Sud and he thanks his hosts for their hospitality and acknowledges partial support by ACI Sécurité Informatique, 2003-n24, projet “Réseaux Quantiques”.

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

VL - 3328

SP - 372

EP - 383

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -

The complexity of the local Hamiltonian problem

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this