⚛️ quantum physics

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

This paper establishes new lower bounds for the Quantum Max Cut problem on graphs by relating them to the Lovász theta function and Shearer's bound, demonstrating that these bounds are achievable by product states and extending previous results on classical Max Cut and triangle-free graphs.

Original authors: Felix Huber

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Felix Huber

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a city planner trying to divide a neighborhood into two teams for a giant game of tag. Your goal is to arrange the houses so that the maximum number of friendships (edges) exist between the two teams, rather than within them. This is the classic "Max Cut" problem.

Now, imagine this neighborhood isn't made of houses and people, but of tiny, invisible quantum particles (qubits) that can be in multiple states at once. This is Quantum Max Cut. Instead of just drawing a line on a map, you have to find the perfect "quantum arrangement" (a state) that maximizes the energy of the system. This is a much harder puzzle because quantum particles are weird and interconnected in ways normal objects aren't.

This paper by Felix Huber is like a master chef revealing a new, reliable recipe for getting a very good score on this quantum puzzle, even if you can't solve the whole thing perfectly.

Here is the breakdown of the paper's main ideas using simple analogies:

1. The "Perfect Map" vs. The "Rough Sketch"

In the classic version of this problem, mathematicians use a tool called the Lovász theta function. Think of this as a "perfect map" of the neighborhood's connections. It tells you the absolute best possible score you could theoretically get if you had infinite computing power.

However, calculating this perfect map is hard. The paper shows that you don't need the perfect map to get a great score. You can use a "rough sketch" (a simpler mathematical bound) to guarantee a specific minimum score.

2. The "Magic Dice" Strategy (Rounding)

How do you get from a complex mathematical map to a real solution? The paper uses a technique called randomized rounding.

Imagine you have a set of arrows pointing in different directions (vectors) representing the quantum particles. To turn these into a concrete answer, the author suggests rolling a set of "magic dice" (random numbers).

You roll the dice to project these arrows onto a new, simpler surface.
This process turns the complex quantum arrows into simple, physical "product states" (think of these as simple, independent settings for each particle, like flipping a switch on or off).
The paper proves that even though you are using a random method, the average result is guaranteed to be very high.

3. The New "Guaranteed Score"

The paper's main achievement is a new formula that guarantees a minimum score for the Quantum Max Cut problem.

The Old Guarantee: If you just guessed randomly, you'd get about 25% of the total possible edges.
The New Guarantee: The author proves you can always get more than that. The exact amount depends on how "connected" the graph is (represented by the Lovász theta function).
The Analogy: If the classic method says, "You can definitely get at least 25% of the points," this paper says, "Actually, based on the shape of the neighborhood, you can guarantee at least 25% plus a bonus chunk. The more 'spread out' the connections are, the bigger the bonus."

4. Why "Triangle-Free" Neighborhoods are Special

The paper also looks at a specific type of neighborhood: one where no three houses are all friends with each other (no "triangles"). In the real world, these are like systems where particles don't form tight little cliques.

For these specific "triangle-free" systems, the author extends a famous result from the 1990s (Shearer's bound).

The Result: For these specific graphs, the paper proves you can get a score that grows slightly faster than just the number of edges.
The Takeaway: It's like saying, "If your neighborhood has no tight-knit cliques, our magic dice strategy works even better, guaranteeing a score that gets stronger as the neighborhood gets larger."

5. The "Product State" Surprise

A key finding is that you don't need a complex, entangled quantum state (where particles are spooky-linked across the whole system) to get this high score.

The Metaphor: You can achieve this high score by treating every particle independently, like a row of light switches that you flip individually.
Why it matters: In the real world, creating complex entangled states is very difficult and expensive. Proving that a simple, "unentangled" strategy is enough to beat the basic random guess is a huge practical win.

Summary

Felix Huber's paper is a mathematical proof that says: "If you want to solve the Quantum Max Cut problem, you don't need a supercomputer to find the perfect answer. You can use a simple, randomized strategy that treats particles individually, and you are mathematically guaranteed to get a score significantly better than a random guess."

It connects the abstract world of quantum physics with the geometry of graphs, showing that even in the quantum realm, simple, independent strategies can be surprisingly powerful.

Technical Summary: Lovász Theta and Shearer Lower Bounds on Quantum Max Cut

Problem Statement
The paper addresses the Quantum Max Cut (QMC) problem, a generalization of the classical Max Cut problem to the domain of quantum many-body physics. While classical Max Cut seeks a partition of a graph's vertices to maximize the number of crossing edges, QMC asks for the largest eigenvalue of the Hamiltonian $H_{qmc} = \frac{1}{4} \sum_{uv \in E} (I - X_u X_v - Y_u Y_v - Z_u Z_v)$ . This Hamiltonian is physically significant as its negative corresponds to the anti-ferromagnetic Heisenberg Hamiltonian, a fundamental model in quantum magnetism. The objective is to establish rigorous lower bounds on the ground state energy (or equivalently, the maximum eigenvalue of $H_{qmc}$ ) for arbitrary graphs, specifically focusing on bounds achievable by product states.

Methodology
The author employs a probabilistic rounding technique adapted from the Briët-de Oliveira Filho-Vallentin (BOV) framework, originally developed for classical approximation algorithms. The core methodology involves:

Vector Representation: Utilizing the Lovász theta function $\vartheta(\bar{G})$ of the graph's complement to assign unit vectors $\{x_u\}$ to vertices such that $\langle x_u, x_v \rangle = -1/(\vartheta(\bar{G}) - 1)$ for all edges $uv \in E(G)$ .
Randomized Rounding: Mapping these high-dimensional vectors to one-qubit states via a random matrix $Z \in \mathbb{R}^{3 \times n}$ with standard normal entries. Specifically, for each vertex $u$ , a unit vector $y_u = Zx_u / \|Zx_u\|$ is generated, defining a product state $\varrho_\vartheta = \bigotimes_{u} \varrho_u$ where $\varrho_u$ is a single-qubit density matrix on the Bloch sphere defined by $y_u$ .
Expectation Analysis: Calculating the expected value of the energy $\mathbb{E}[\text{tr}(H_{qmc} \varrho_\vartheta)]$ . This requires evaluating the expectation of the dot product of the rounded vectors, $\mathbb{E}[y_u \cdot y_v]$ , which relates to the inner product of the original vectors via a hypergeometric function $\hat{F}(r, u \cdot v)$ .
Inequality Derivation: The proof relies on establishing specific inequalities for the function $\hat{F}(r, \alpha)$ (where $r=3$ for the full QMC Hamiltonian) that generalize known properties of the arcsine function used in classical Max Cut analysis.

Key Contributions and Results

Lovász Theta Lower Bound:
The primary result is a new lower bound for the QMC value $qmc(G)$ of a graph with $m$ edges:
$qmc(G) \geq \frac{m}{4} \left( 1 + \frac{8}{3\pi} \frac{1}{\vartheta(\bar{G}) - 1} \right)$
This bound is achieved by a product state. The proof extends a result by Balla, Janzer, and Sudakov [BJS24] on classical Max Cut. The author notes that the coefficient $\frac{8}{3\pi} \approx 0.8488$ is strictly larger than the classical coefficient $\frac{2}{\pi} \approx 0.6366$ , indicating that the quantum rounding strategy outperforms the classical one in this context.
- Vector Chromatic Number: The bound can be strengthened by replacing $\vartheta(\bar{G})$ with the vector chromatic number $\chi_{vec}(G)$ , as $\chi_{vec}(G) \leq \vartheta(\bar{G})$ .
- Degree-Based Relaxation: For graphs with maximum degree $\Delta$ , using the relation $\vartheta(\bar{G}) \leq \Delta + 1$ , the bound relaxes to $qmc(G) \geq \frac{m}{4} (1 + \frac{8}{3\pi\Delta})$ . This is highlighted as particularly relevant for bounded-degree graphs common in quantum physics (e.g., lattices).
Shearer-Type Lower Bound for Triangle-Free Graphs:
The paper extends results by Carlson et al. and Shearer to the quantum setting. By constructing specific vector ansatzes based on the semi-definite programming (SDP) relaxation of classical Max Cut, the author derives a quantum analogue of Shearer's bound.
- For triangle-free graphs with $m$ edges, the paper proves:
  $qmc(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3\pi}$
- This result is derived by generalizing inequalities involving the arcsine function to the hypergeometric function $\hat{F}(3, \cdot)$ , specifically proving that $\hat{F}(3, \alpha - \beta) \leq \frac{3\pi}{8}(\alpha - \beta)$ for non-negative $\alpha, \beta$ .

Significance and Claims
The paper claims to provide the first explicit lower bounds for Quantum Max Cut that are expressed in terms of graph invariants like the Lovász theta function and the Shearer bound, analogous to classical results. The significance lies in:

Theoretical Unification: Bridging the gap between classical approximation algorithms (Max Cut) and quantum many-body problems (Heisenberg Hamiltonian) by adapting classical rounding techniques to the quantum operator setting.
Product State Optimality: Demonstrating that these non-trivial lower bounds can be achieved by simple product states, which are computationally efficient to prepare and analyze, rather than requiring complex entangled states.
Physical Relevance: The degree-dependent bound offers a practical tool for estimating ground state energies in physically relevant systems with bounded connectivity, such as lattices with defects.

The author explicitly states that the proof technique can be adapted to Hamiltonians containing only subsets of the QMC terms (e.g., $H_{XX}$ ), yielding different coefficients based on the dimension $r$ of the rounding space. The work does not propose new experimental setups or future algorithmic developments beyond these theoretical bounds.