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.
- http://www.lri.fr/~kempe - personal webpage