Lov\'asz theta and Shearer lower bounds on Quantum Max Cut

Quantum Max Cut is a problem relevant to computer science and many-body quantum physics due to its links to classical Max Cut and the anti-ferromagnetic Heisenberg Hamiltonian.

We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement.

For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3\pi}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state.

The proof can be strenghtened by the vector chromatic number and extends a result by Balla, Janzer, and Sudakov on classical Max Cut.

A relaxed bound follows from $\vartheta(\bar{G}) - 1 \leq \Delta$ for graphs with maximum degree $\Delta$, making it interesting for practically relevant quantum many-body systems.

We also extend results by Carlson et al. and Shearer and show that $\text{qmc}(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3 \pi}$ for all triangle-free graphs with $m$ edges.