The Complexity of the Local Hamiltonian Problem
| dc.creator | Kempe, Julia | |
| dc.creator | Kitaev, Alexei | |
| dc.creator | Regev, Oded | |
| dc.date | 2004-06-24 | |
| dc.date | 2005-10-02 | |
| dc.date.accessioned | 2026-07-07T06:27:00Z | |
| dc.date.available | 2026-07-07T06:27:00Z | |
| dc.description | 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 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 two-local interactions on qubits is equivalent to standard quantum computation. | |
| dc.description | 30 pages, 3 figures, replaced with revised version, numerous improvements to readability and expanded adiabatic section | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0406180 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0406180 | |
| dc.identifier | SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006), conference version in Proc. 24th FSTTCS, p. 372-383 (2004) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/97289 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | The Complexity of the Local Hamiltonian Problem | |
| dc.type | text |