Skip to main content

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.

Speaker bio

Ashley Montanaro completed his PhD in quantum computing at the University of Bristol in 2008 under the supervision of Richard Jozsa. After some time as an EPSRC Postdoctoral Fellow at the Centre for Quantum Information and Foundations in Cambridge, he has recently returned to Bristol as a Lecturer in the Department of Computer Science.

Share this: