A Caltech Library Service

The Complexity of the Local Hamiltonian Problem

Kempe, Julia and Kitaev, Alexei and Regev, Oded (2004) The Complexity of the Local Hamiltonian Problem. In: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. No.3328. Springer , Berlin, pp. 372-383. ISBN 978-3-540-24058-7.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article Paper ReadCube access
Additional Information:© 2004 Springer-Verlag Berlin Heidelberg. 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”.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
ACI Sécurité InformatiqueACI-CR 2002-40
European UnionRESQ IST-2001-37559
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)F30602-01-2-0524
Office of Naval Research (ONR)FDN-00014-01-1-0826
Tel-Aviv UniversityUNSPECIFIED
Army Research Office (ARO)DAAD19-03-1-0082
Series Name:Lecture Notes in Computer Science
Issue or Number:3328
Record Number:CaltechAUTHORS:20191011-072647725
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99231
Deposited By: Tony Diaz
Deposited On:11 Oct 2019 17:04
Last Modified:16 Nov 2021 17:44

Repository Staff Only: item control page