Skip to content



The complexity of local Hamiltonians

Kempe, J (Paris-Sud)
Tuesday 24 August 2004, 10:10-11:00

Seminar Room 1, Newton Institute


This is joint work with Alexei Kitaev and Oded Regev.

Complexity theory formalises the notion of an _efficient_ algorithm. A major challenge for complexity theory is to understand the interrelation between classical and the newly emerging quantum complexity classes.

The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It had been known that 3-local Hamiltonian is QMA-complete; whereas 1-local Hamiltonian is in P, efficiently solvable and hence not believed to be QMA-complete. The exact complexity of the 2-local problem has so far been unknown.

We will introduce rigorous perturbation theory techniques to complexity theory and show that 2-local Hamiltonian is QMA complete. Our techniques also show that 2-local _adiabatic_ computation on qubits is equivalent to standard quantum computation. We hope that our physics inspired technique might prove useful elsewhere in (quantum) computer science. We outline some open problems and future directions.

Related Links


[ppt ]


MP3MP3 Real AudioReal Audio

Back to top ∧