2025/12/23 by Felix Huber, Huber, Felix
Computer Science · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2512.20326
openalex publication_date 2025/12/23 · openalex created_date 2025/12/25 · openalex updated_date 2026/07/28
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, qmc(G) ≥ \tfracm4( 1 + \tfrac83π\tfrac1ϑ(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 ϑ(G) - 1 ≤ Δ for graphs with maximum degree Δ, making it interesting for practically relevant quantum many-body systems. We also extend results by Carlson et al. and Shearer and show that qmc(G) ≥ (m)/(4) + \frac2m3/43 π for all triangle-free graphs with m edges.