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. https://resolver.caltech.edu/CaltechAUTHORS:20191011-072647725
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
See Usage Policy. 345kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191011-072647725
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.
| Item Type: | Book Section | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||||||||
| 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 | ||||||||||||||||||
| Funders: |
| ||||||||||||||||||
| Series Name: | Lecture Notes in Computer Science | ||||||||||||||||||
| Issue or Number: | 3328 | ||||||||||||||||||
| DOI: | 10.1007/978-3-540-30538-5_31 | ||||||||||||||||||
| Record Number: | CaltechAUTHORS:20191011-072647725 | ||||||||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20191011-072647725 | ||||||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||
| ID Code: | 99231 | ||||||||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||||||||
| Deposited By: | Tony Diaz | ||||||||||||||||||
| Deposited On: | 11 Oct 2019 17:04 | ||||||||||||||||||
| Last Modified: | 16 Nov 2021 17:44 |
Repository Staff Only: item control page
