Kempe, Julia and Kitaev, Alexei and Regev, Oded (2006) The Complexity of the Local Hamiltonian Problem. SIAM Journal on Computing, 35 (5). pp. 1070-1097. ISSN 0097-5397. doi:10.1137/S0097539704445226. https://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 304kB | |
|
PDF
- Submitted Version
See Usage Policy. 345kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06
Abstract
The k-LOCAL Hamiltonian problem is a 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.
| Item Type: | Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||
| Additional Information: | © 2006 SIAM Received by the editors July 20, 2004; accepted for publication (in revised form) June 23, 2005; published electronically March 3, 2006. A preliminary version of this paper appeared in Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2004. This author’s [JK] work was 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; by DARPA and Air Force Laboratory, Air Force Materiel Command, USAF, under agreement F30602-01-2-0524; by DARPA and the Office of Naval Research under grant 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. This author’s [AK] work was supported in part by the National Science Foundation under grant EIA-0086038. This author’s [OR] work was supported by an Alon Fellowship, the Binational Science Foundation, the Israel Science Foundation, and the Army Research Office grant DAAD19-03-1-0082 and partly supported by ACI Sécurité Informatique, 2003-n24, projet “Réseaux Quantiques.” Part of this author’s work was carried out during a visit at LRI, Université de Paris-Sud, and he thanks his hosts for their hospitality. Discussions with Sergey Bravyi and Frank Verstraete are gratefully acknowledged. | ||||||||||||
| Subject Keywords: | quantum computation, local Hamiltonian problem, complete problems, adiabatic computation | ||||||||||||
| Issue or Number: | 5 | ||||||||||||
| DOI: | 10.1137/S0097539704445226 | ||||||||||||
| Record Number: | CaltechAUTHORS:KEMsiamjc06 | ||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06 | ||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
| ID Code: | 3919 | ||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||
| Deposited By: | Archive Administrator | ||||||||||||
| Deposited On: | 19 Jul 2006 | ||||||||||||
| Last Modified: | 08 Nov 2021 20:13 |
Repository Staff Only: item control page
