Complexity classification of local Hamiltonian problems
Ashley Montenaro ( University of Bristol )

14:00 28th January 2014 ( week 2, Hilary Term 2014 )Lecture Theatre B
Schaefer's dichotomy theorem is a remarkable result which completely characterises the complexity of families of boolean
constraint satisfaction problems as either being in P or NPcomplete. In this talk, I will discuss an analogue of this result
in quantum computation.
The natural quantum analogue of classical constraint satisfaction problems is the socalled local Hamiltonian problem,
or in other words the calculation of groundstate energies of physical systems. The most general form of this problem is known
to be QMAcomplete, where QMA is the quantum analogue of NP. One way of making the problem more physically meaningful is to
restrict the Hamiltonian in question by picking its terms from a fixed set S, which can dramatically change its complexity.
Examples of such special cases are the Heisenberg and Ising models from condensedmatter physics.
I will describe a characterisation of the complexity of restricted local Hamiltonian problems for all 2local qubit Hamiltonians.
Depending on the subset S, the problem falls into one of the following categories: in P; NPcomplete; polynomialtime equivalent
to the Ising model with transverse magnetic fields; or QMAcomplete.
This talk will aim to be accessible to a general audience of computer scientists, and is based on joint work with Toby
Cubitt.