# Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut

arXiv: https://arxiv.org/abs/1909.08846 · HTML: https://mlsanity.com/paper/1909.08846/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks](https://mlsanity.com/paper/2309.07250/) (2023)

## Abstract (arXiv)

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.