Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. A natural generalization of constraint satisfaction problems to the quantum setting is the local Hamiltonian problem, which is of significant interest to both complexity theorists and to physicists studying properties of physical systems alike. In this talk, we define a natural approximation version of the local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result, which builds on the first one, gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem.
The latter result is based on an adaptation of the “exhaustive sampling method” by Arora et al. [J. Comp. Sys. Sci., vol. 58, 1999] to the quantum setting, and might be of independent interest.
This talk is based on joint work with Julia Kempe. The presentation will be geared to both computer scientists and physicists alike.