⚛️ quantum physics

An improved Quantum Max Cut approximation via matching

This paper presents a classical approximation algorithm for the Quantum Max Cut problem that achieves a 0.595 approximation ratio by utilizing maximum weighted matching to generate simpler product states of at most two qubits, thereby outperforming previous best results.

Original authors: Eunou Lee, Ojas Parekh

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eunou Lee, Ojas Parekh

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 trying to organize a massive, chaotic party where the guests are tiny, invisible particles called qubits. The goal of this party is to get everyone to "dance" in a way that creates the most energy possible. In the world of quantum physics, this is called finding the maximum energy state of a system.

This specific party game is called Quantum Max Cut. It's a bit like the classic "Max Cut" game you might know from computer science, but instead of just flipping switches on or off, the guests (qubits) can be in superpositions of states and can even get "entangled" (a spooky connection where two particles act as one).

The problem is: figuring out the perfect dance routine for millions of particles is incredibly hard. Even the world's fastest supercomputers struggle with it. So, scientists try to find approximations—good enough solutions that are easy to calculate.

Here is a breakdown of what this new paper does, using simple analogies:

1. The Old Way: The "Perfect Dance" Problem

Previously, the best algorithms tried to solve this by looking at the whole party at once. They used complex math (called Semidefinite Programming) to predict how every single guest should move.

The Catch: To get a really good score, these algorithms had to create entangled states. Imagine trying to choreograph a dance where Guest A is holding hands with Guest B, who is holding hands with Guest C, all the way across the room. It's beautiful, but it's incredibly difficult to calculate and execute.
The Score: The best previous method could guarantee a score of about 56.2% of the perfect energy.

2. The New Idea: "Pair Up and Ignore the Rest"

The authors, Eunou Lee and Ojas Parekh, decided to try a much simpler strategy. Instead of trying to choreograph the whole room, they asked: "What if we just pair up the guests who get along best, and let the rest chill out?"

They used a classic computer science trick called Maximum Weight Matching.

The Analogy: Imagine you have a room full of people, and every pair of people has a "friendship score" (weight). You want to pair them up so that the total friendship score of all pairs is as high as possible.
The Rule: You can't have one person in two pairs at once.
The Result: You find the best possible pairs. For these pairs, you assign them a special "perfect dance" move (called a singlet state). For everyone who didn't get paired up, you just tell them to sit in a chair and spin randomly (a mixed state).

3. The Secret Sauce: Why It Works Better

You might think, "But ignoring the unpaired guests sounds like a bad idea!" And usually, it would be. However, the authors realized something clever:

The "Monogamy" Rule: In quantum physics, there's a rule called the "Monogamy of Entanglement." It basically says: If Particle A is super-duper entangled with Particle B, it can't be very entangled with Particle C.
The Insight: The authors realized that the "perfect pairs" strategy (Maximum Matching) naturally respects this rule. If you pair up the strongest connections, you aren't violating the laws of physics.
The Hybrid Approach: They didn't just rely on pairing. They ran two simulations:
1. The "Product State" Method: A standard method where everyone dances independently (no holding hands).
2. The "Matching" Method: The new method where we pair up the best friends.
- The Winner: They simply picked whichever of the two results gave the higher energy score.

4. The Result: A New Record

By combining these two simple ideas, they achieved a new record-breaking score:

Old Best: ~56.2% (for general graphs).
New Best: 59.5%.

This is a big deal because:

It's Simpler: The new algorithm doesn't need to calculate complex, global entanglement for the whole room. It just finds the best pairs (which is a very fast, easy calculation) and picks the better of two simple options.
It's Better: It guarantees a higher energy state than any previous method, even those that tried to be more "quantum" by entangling everyone.

The Big Picture

Think of this like trying to fix a broken machine.

Old Approach: You try to understand every single gear, spring, and wire simultaneously to build a perfect replica. It's hard, and you only get 56% of the machine working.
New Approach: You look at the machine, find the two gears that are most critical and fix them together perfectly. You leave the other gears loose. Then, you compare that to a different simple fix. You pick the best one.
The Surprise: This "lazy" approach actually works better than the complex one, achieving 59.5% efficiency.

Why does this matter?
This proves that sometimes, you don't need to be a quantum wizard to solve quantum problems. Simple, clever classical tricks (like finding the best pairs) can outperform complex quantum simulations. This brings us one step closer to understanding how to get a "quantum advantage"—solving problems faster or better than classical computers can.

1. Problem Definition: Quantum Max Cut (QMC)

The paper addresses the Quantum Max Cut (QMC) problem, a quantum optimization benchmark defined on an $n$ -qubit system.

Objective: Given a weighted graph $G=(V, E, w)$ , find a quantum state $|\psi\rangle$ that maximizes the energy of the antiferromagnetic Heisenberg Hamiltonian:
$H = \sum_{(i,j) \in E} w_{ij} \frac{I - X_iX_j - Y_iY_j - Z_iZ_j}{4}$
where $X_i, Y_i, Z_i$ are Pauli matrices acting on qubit $i$ .
Complexity: Finding the exact maximum energy state is QMA-hard. Therefore, the goal is to design classical approximation algorithms that output a description of a quantum state with an energy guaranteed to be a certain fraction ( $\alpha$ ) of the optimal energy ( $\lambda_{\max}(H)$ ).
Context: Previous algorithms typically rely on the Goemans-Williamson framework: relaxing the problem to a Semidefinite Program (SDP), solving it, and "rounding" the solution to a feasible quantum state.

2. Methodology

The authors propose a novel classical approximation algorithm that diverges from previous SDP-rounding approaches by utilizing Maximum Weight Matching (MWM) to generate entangled states, rather than relying on complex entanglement structures derived directly from SDP vectors.

The Algorithm (Algorithm 1)

The algorithm computes two candidate states and outputs the one with the higher energy:

Product State ( $\rho_1$ ):
- Solves the Level-2 Quantum Lasserre SDP.
- Extracts vectors corresponding to single-qubit Paulis ( $v(X_i), v(Y_i), v(Z_i)$ ).
- Applies the Gharibian-Parekh rounding technique (randomized rounding) to generate a product state (a tensor product of 1-qubit states).
Matching State ( $\rho_2$ ):
- Ignores the SDP solution for state construction.
- Solves the Maximum Weight Matching (MWM) problem on the input graph $G$ (e.g., using Edmonds' algorithm).
- Constructs a state where:
  - For every edge $(i,j)$ in the matching $M$ , the qubits are assigned the singlet state (maximally entangled 2-qubit state): $\frac{|01\rangle - |10\rangle}{\sqrt{2}}$ .
  - For unmatched qubits, the state is the maximally mixed 1-qubit state ( $I/2$ ).
- The total state is the tensor product of these local states.

Theoretical Foundation

The core innovation lies in relating the Level-2 SDP solution to the Maximum Weight Matching value without needing to round the SDP into an entangled state directly.

Monogamy of Entanglement: The authors leverage constraints on the SDP variables (specifically $h_{ij}^+$ , derived from the SDP solution) which represent the "potential" for entanglement on an edge.
Convexgamy: They introduce a new concept called "entanglement convexgamy" (Lemma 3), which provides tighter, non-linear bounds on the feasible region of entanglement values on star graphs and triangles compared to the linear "monogamy" bounds used previously.
LP Relaxation: They prove that the values $h_{ij}^+$ derived from the SDP satisfy the constraints of the Linear Programming (LP) relaxation for Maximum Weight Matching, up to a scaling factor of $4/5$ . This allows them to bound the weight of the optimal matching against the SDP objective.

3. Key Contributions

New Approximation Ratio: The algorithm achieves an approximation ratio of 0.595.
- This improves upon the previous best for general graphs (Lee [10], ratio 0.562).
- This improves upon the previous best for triangle-free graphs (King [8], ratio 0.582).
Simplification of Entangled State Generation:
- Previous best algorithms for QMC that output entangled states required complex rounding procedures based on the full Level-2 SDP solution.
- This algorithm generates the entangled component ( $\rho_2$ ) purely via Maximum Weight Matching, a classical combinatorial problem solvable in polynomial time, independent of the SDP solution.
- The SDP is only used to bound the performance of the product state ( $\rho_1$ ) and to prove the theoretical guarantee for the matching state.
Theoretical Insight (Convexgamy): The paper derives tighter non-linear inequalities (Lemma 2 and Lemma 3) describing the feasible space of entanglement on small subgraphs (triangles and 2-edge stars), termed "entanglement convexgamy." This provides a more precise characterization of the SDP feasible region than previous linear monogamy constraints.

4. Results and Analysis

Performance Guarantee: The authors prove that for any input graph, the energy of the output state $\sigma$ satisfies:
$\text{Energy}(\sigma) \geq 0.595 \times \lambda_{\max}(H)$
Mechanism of Improvement: The improvement comes from the fact that the Maximum Weight Matching provides a "safety net." If the product state rounding ( $\rho_1$ ) performs poorly (which happens when the SDP suggests high entanglement), the matching state ( $\rho_2$ ) is guaranteed to capture a significant portion of the energy because the SDP variables $h_{ij}^+$ form a fractional matching that is close to an integral matching.
Optimality of the Approach: The authors note that even if one could solve the LP perfectly (scaling factor $\alpha=1$ ), the theoretical limit of this specific approach would be 0.606. Thus, the gap between their result (0.595) and the theoretical limit of the method is small.

5. Significance

Practicality: The algorithm is computationally efficient. While it solves an SDP, the generation of the entangled state does not require complex quantum state synthesis from SDP vectors; it relies on standard graph matching algorithms.
Conceptual Shift: It challenges the assumption that high-quality approximations for QMC must rely on complex, globally entangled ansatzes derived directly from SDP rounding. It demonstrates that simple, structured states (products of singlets and mixed states) can outperform more complex entangled states if the graph structure (matching) is exploited correctly.
Future Directions: The paper opens new avenues for research, including:
- Finding rigorous quantum algorithms (e.g., VQE) that might surpass classical bounds.
- Investigating whether higher levels of the Lasserre hierarchy can yield better "convexgamy" relations to push the approximation ratio closer to the theoretical limit.
- Defining clearer criteria for what constitutes a "classical" algorithm solving a quantum optimization problem (Definition 2 in the paper).

In summary, Lee and Parekh present a streamlined, high-performance algorithm for Quantum Max Cut that combines SDP-based product state rounding with a Maximum Weight Matching strategy, achieving a new state-of-the-art approximation ratio of 0.595 while significantly simplifying the construction of entangled output states.