Lovász theta and Shearer lower bounds on Quantum Max Cut

Abstract

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)\ge \frac{m}{4}(1+\frac{8}{3\pi }\frac{1}{\vartheta (\bar{G})-1})$, 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\le \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)\ge \frac{m}{4}+\frac{2m^{3/4}}{3\pi }$ for all triangle-free graphs with $m$ edges.

8 pages, comments welcome. v2: Shearer-type lower bound added