The Complexity of the Local Hamiltonian Problem
- Creators
- Kempe, Julia
-
Kitaev, Alexei
- Regev, Oded
- Others:
- Lodaya, Kamal
- Mahajan, Meena
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.
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".Attached Files
Submitted - 0406180.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:be47874f6db003f5da36fcf136f5981b
|
345.6 kB | Preview Download |
Additional details
- Eprint ID
- 99231
- Resolver ID
- CaltechAUTHORS:20191011-072647725
- ACI Sécurité Informatique
- ACI-CR 2002-40
- European Union
- RESQ IST-2001-37559
- Defense Advanced Research Projects Agency (DARPA)
- Air Force Office of Scientific Research (AFOSR)
- F30602-01-2-0524
- Office of Naval Research (ONR)
- FDN-00014-01-1-0826
- NSF
- EIA-0086038
- Tel-Aviv University
- Army Research Office (ARO)
- DAAD19-03-1-0082
- Created
-
2019-10-11Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 3328