← Back to papers
A Lovász theta lower bound on Quantum Max Cut
Felix Huber·December 23, 2025
Quantum Physicsmath.CO
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut.