Complexity classification of local Hamiltonian problems
Ashley Montenaro ( University of Bristol )
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 NP-complete. 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 so-called local Hamiltonian problem, or in other words the calculation of ground-state energies of physical systems. The most general form of this problem is known to be QMA-complete, 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 condensed-matter physics.
I will describe a characterisation of the complexity of restricted local Hamiltonian problems for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete.
This talk will aim to be accessible to a general audience of computer scientists, and is based on joint work with Toby Cubitt.