  Approximation algorithms for constraint satisfaction problems (CSPs) are a
central direction of study in theoretical computer science. In this work, we
study classical product state approximation algorithms for a physically
motivated quantum generalization of Max-Cut, known as the quantum Heisenberg
model. This model is notoriously difficult to solve exactly, even on bipartite
graphs, in stark contrast to the classical setting of Max-Cut. Here we show,
for any interaction graph, how to classically and efficiently obtain
approximation ratios 0.649 (anti-ferromagnetic XY model) and 0.498
(anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show
that the best possible ratios achievable by a product state for these models is
2/3 and 1/2, respectively.
