Prof. Daniel Gottesman

Perimeter Institute
Waterloo Canada

1-dimensional spin chains are hard

Abstract:

Kitaev defined a complexity class QMA ("Quantum Merlin-Arthur"), which is essentially the quantum version of the class NP: QMA is, roughly speaking, the set of problems where the answer may be difficult to find, but is easy to check on a quantum computer. As with NP, QMA has complete problems; if you can solve a QMA-complete problem, you can solve any problem in QMA. In particular, Kitaev showed that the 5-local Hamiltonian problem, which asks for the ground state energy of a Hamiltonian interacting up to 5 qubits in a term, is QMA-complete. A series of later results improved this to show that finding the ground state energy remains QMA-complete even for a Hamiltonian only interacting nearest-neighbor qubits in a 2-dimensional lattice. In this talk, I will sketch a proof that nearest-neighbor interactions in a line are sufficient. The individual particles are not qubits now, but 12-state systems. This result implies that there can exist 1-dimensional systems that cannot relax to their own ground states in a reasonable amount of time.

Seminar schedule: http://www.physics.rutgers.edu/qcg/Seminars.html