Description
Approximation algorithms for the quantum Heisenberg model
The Goemans-Williamson algorithm for MAX CUT is a celebrated achievement in the study of approximation algorithms for constraint satisfaction problems. Here, we study a physically motivated local Hamiltonian model which captures a genuinely quantum notion of MAX CUT: The anti-ferromagnetic quantum Heisenberg model. In particular,we generalize the Goemans-Williamson algorithm to obtain classical polynomial-time approximation algorithms for both the Heisenberg anti-ferromagnet and XY models. To rigorously establish the approximation precision of these algorithms, we uncover connections between MAX CUT and these models to obtain tight bounds on the strength of mean field (a.k.a. product state) ansatzes. Our results yield the first known approximation algorithms for a quantum local Hamiltonian model which apply to arbitrary interaction graphs.
This talk is based on joint work with Yi-Kai Liu, and is a project in progress.