The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Workshop

Quantum Information Theory: Present Status and Future Directions

The Complexity of Local Hamiltonians

24th August 2004

Author: Julia Kempe (CNRS & LRI-Orsay)


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