⚛️ quantum physics

Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

This paper establishes new monogamy of entanglement bounds for two-local qudit Hamiltonians and introduces matching-based algorithms that significantly improve approximation guarantees for maximum energy, achieving ratios of $1/d$ for general graphs and $0.595$ for qubits, thereby outperforming previous random assignment and algorithmic approaches.

Original authors: Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, Stuart Wayland

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, Stuart Wayland

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

The Big Picture: The Quantum Party Problem

Imagine you are hosting a massive, chaotic party where the guests are quantum particles (specifically, "qudits," which are like super-charged dice that can land on $d$ different sides instead of just 2).

The goal of the party is to get everyone to "dance" together in a way that generates the maximum amount of energy (or excitement). In physics, this is called finding the "most excited state" of a system.

However, there's a catch: The Monogamy of Entanglement.
Think of "entanglement" as a deep, intimate dance between two particles. The "Monogamy" rule says: If Particle A is dancing intimately with Particle B, it cannot be dancing intimately with Particle C at the same time. You can't be best friends with everyone simultaneously in the quantum world.

The problem the authors are solving is: How do we organize this party to get the most energy out of it, knowing that particles can't be best friends with everyone?

The Challenge: It's Too Complicated to Solve Perfectly

In the classical world (like a normal party), we have algorithms to figure out the best seating chart. But in the quantum world, this problem is incredibly hard (mathematically "QMA-hard"). It's like trying to solve a puzzle where the pieces keep changing shape and the rules of physics get in the way.

Because we can't solve it perfectly every time, computer scientists use approximation algorithms. These are like "good enough" strategies.

The Old Strategy (Random Assignment): Imagine throwing darts at a dartboard to decide who dances with whom. On average, this gets you about $1/d^2$ of the maximum possible energy. It's okay, but not great.
The New Strategy (The Matching Algorithm): The authors propose a smarter way to pair people up.

The Solution: The "Matchmaker" Algorithm

The authors introduce a simple, clever algorithm based on Maximum Matching.

The Analogy:
Imagine you are a matchmaker at a speed-dating event. You have a list of people (vertices) and a list of who wants to dance with whom (edges).

The Rule: You can't have one person dancing with two people at once.
The Move: You find the largest possible group of pairs where everyone has exactly one partner. This is called a "Maximum Matching."
The Result: You tell those pairs to dance the "Maximally Entangled" dance (the most intimate quantum dance possible). Everyone else just stands around doing nothing (or dancing randomly).

Why is this better?
The authors proved that this simple "Matchmaker" strategy is much better than throwing darts.

General Graphs: It guarantees you get at least $1/d$ of the maximum energy. (If $d=2$ , that's 50%, which is double the random guess!).
Bounded Degree Graphs: If the party isn't too crowded (no one is trying to dance with too many people), the algorithm gets even better, guaranteeing more than 50% of the maximum energy, regardless of how complex the quantum rules are.

The Secret Weapon: "Monogamy Certificates"

How did they prove their algorithm is good? They had to prove a limit on how much "intimacy" (energy) can exist in the system.

They used a mathematical tool called Sum-of-Squares (SOS) proofs. Think of this as a Mathematical Inspector.

The Inspector looks at the party and says, "Hey, because of the Monogamy rule, you can't have more than X amount of total energy, even if you try your hardest."
They proved that the total energy is capped by the size of the "Maximum Matching" (the number of pairs you can make).
This "certificate" acts like a speed limit sign. It tells the algorithm: "You can't go faster than this, but you can definitely reach this speed."

Special Cases: When the Dice are Just Coins ( $d=2$ )

When the particles are simple qubits (like coins, $d=2$ ), the problem becomes even more famous. It's known as the Quantum Max-Cut problem.

Previous Best: The best known algorithm before this paper got about 59.5% of the maximum energy.
The New Result: By combining their "Matchmaker" strategy with a slightly different "Product State" strategy (where everyone just picks a side and sticks to it), they improved the guarantee to 0.599 (almost 60%).
The EPR Problem: For a specific type of quantum problem called the EPR problem, they improved the guarantee from roughly 70.7% to 72%.

Why Does This Matter?

Better Quantum Computers: As we build real quantum computers, we need to know how well they can solve problems. This paper gives us a "floor" (a guaranteed minimum performance) for how well we can approximate these solutions without needing a super-computer.
Understanding Entanglement: It helps us understand the "limits of friendship" in the quantum world. It proves that even in a chaotic quantum system, simple pairing strategies work surprisingly well.
Beating Randomness: It shows that you don't need complex, heavy-duty math (like Semidefinite Programming) to get good results. Sometimes, a simple "pair them up" approach is the most efficient way to go.

Summary in a Nutshell

The authors took a very hard quantum physics problem (finding the most energetic state of a system) and showed that a simple pairing strategy works much better than random guessing. They used new mathematical "speed limit" proofs to show exactly how good this strategy is. In the process, they slightly improved the best-known scores for solving these problems on quantum computers, proving that sometimes, the simplest solution is the most powerful.

1. Problem Definition: The Maximal Entanglement Problem

The paper addresses a specific subclass of the 2-Local Hamiltonian (2-LH) problem, termed the Maximal Entanglement (ME) problem.

Context: Given a system of $n$ qudits (local dimension $d$ ), the goal is to find the maximum energy (most excited state) of a Hamiltonian $H$ .
Structure: The Hamiltonian is a sum of rank-1 projectors onto maximally entangled states defined over the edges of an interaction graph $G=(V, E)$ $G = (V, E)$ .
- $H = \sum_{e \in E} w_e |\psi_e\rangle\langle\psi_e|$ , where $|\psi_e\rangle$ is a maximally entangled state on the two qudits connected by edge $e$ .
- These states are generated via local unitaries $U_e \in SU(d)$ acting on a generalized EPR state: $|\psi_e\rangle = (I \otimes U_e)|EPR_d\rangle$ .
Special Cases:
- EPR Problem: All $U_e = I$ . This is stoquastic and belongs to the class StoqMA.
- Quantum Max-Cut (QMC): For qubits ( $d=2$ ) with $U_e = iY$ . This is QMA-hard.
Objective: Approximate the maximum eigenvalue $\lambda_{\max}(H)$ efficiently. The paper seeks to beat the trivial "random assignment" (maximally mixed state) approximation ratio of $1/d^2$ .

2. Methodology

The authors employ a hybrid approach combining combinatorial algorithms with algebraic proof techniques from the Sum-of-Squares (SOS) hierarchy.

A. Monogamy of Entanglement Certificates (SOS)

The core theoretical contribution is the derivation of new upper bounds on the energy of quantum states using degree-6 Sum-of-Squares (SOS) proofs (equivalent to the level-3 quantum Lasserre SDP).

Star Bound: For any vertex $a$ and its neighbor set $S$ , the expected energy contribution is bounded by:
$\text{Tr}\left(\rho \sum_{b \in S} h_{ab}\right) \leq \frac{|S|}{d} + \frac{d-1}{d}$
Triangle Bound: For any triangle $\{a, b, c\}$ , the energy is bounded by:
$\text{Tr}\left(\rho (h_{ab} + h_{bc} + h_{ac})\right) \leq \frac{3}{d} + \frac{d-1}{d}$
These bounds formalize the "monogamy of entanglement" principle: a qudit cannot be maximally entangled with many neighbors simultaneously. The authors prove these bounds are tight for the EPR problem on star graphs.

B. The Matching-Based Algorithm

The authors propose a simple, efficient algorithm (Algorithm 4.1) that does not use an SDP solver but relies on the Edmonds' Blossom algorithm for finding maximum matchings.

Compute a maximum matching $M$ on the interaction graph $G$ .
For every edge $(u, v) \in M$ , prepare the maximally entangled state $|\psi_{uv}\rangle$ .
For vertices not in the matching, assign the maximally mixed state.
Output the tensor product of these states.

C. Analysis Framework

The analysis connects the SOS certificates to the algorithm's performance:

They define scalar variables $x_{uv} = \text{Tr}(\tilde{\rho} h_{uv})$ derived from a degree-6 pseudo-density matrix $\tilde{\rho}$ .
They prove that these scalars satisfy constraints similar to those in the Edmonds' matching polytope (specifically, constraints on stars and triangles).
Using a lemma from Edmonds (1965) and Lee & Parekh (2024), they relate the expected value of the matching to the maximum matching size, $\text{OPTMatch}(G)$ .
They combine the SOS upper bound on the optimal energy with the lower bound on the algorithm's energy to derive approximation ratios.

3. Key Contributions and Results

General Graphs (Theorems A & B)

Upper Bound: The maximum energy of any ME instance is bounded by $\frac{1}{d} + \frac{5(d-1)}{4d} \text{OPTMatch}(G)$ .
Approximation Guarantee: The matching-based algorithm achieves an approximation ratio of at least $1/d$ for general graphs.
Bounded Degree: For graphs with maximum degree $D$ , the ratio improves to $1/d + \Theta(1/D)$ .
Significance: This strictly outperforms the random assignment strategy (which achieves $1/d^2$ ) and product state algorithms in the bounded degree regime.

Regular Graphs (Corollary 4.11)

For $D$ -regular graphs where $D \leq 5$ and any local dimension $d \geq 2$ , the algorithm guarantees an approximation ratio strictly greater than $1/2$ .

The Qubit Case ( $d=2$ )

When restricted to qubits, the authors combine the matching algorithm with a product-state rounding algorithm (based on [PT21b]) and select the solution with higher energy.

General Qubit ME: Achieves an approximation ratio of 0.595, improving upon the previous best of $0.5$ [PT22].
Quantum Max-Cut (QMC): Improves the analysis of the Lee-Parekh algorithm, showing a guarantee of 0.599 (previously known as 0.595).
EPR Problem: Achieves a guarantee of 0.72 ( $18/25$ ), beating the previous best of $1/\sqrt{2} \approx 0.707$ [Kin23].

4. Significance and Implications

Entanglement Limits: The work provides rigorous, computable upper bounds on the "amount of entanglement" (energy) possible in quantum states over specific graph topologies. The SOS certificates serve as a proxy for quantifying entanglement limits.
Algorithmic Efficiency: It demonstrates that simple combinatorial structures (matchings) can capture non-trivial quantum correlations, avoiding the computational overhead of high-level SDPs for certain approximation guarantees.
Bridging Classical and Quantum: The results draw a parallel between the Unique Games Conjecture (classical) and the limits of entanglement in quantum systems. The matching-based approach mirrors techniques used in classical CSPs but adapts them to the quantum setting via SOS proofs.
NLTS Candidates: The authors suggest that if these bounds are tight and product state approximations cannot be improved further, instances of the Maximal Entanglement problem could serve as candidates for No Low-Energy Trivial States (NLTS), a key concept in quantum complexity theory related to the quantum PCP conjecture.

5. Conclusion

The paper establishes that for 2-local Hamiltonians composed of maximally entangled projectors, the maximum energy is fundamentally limited by the graph's matching structure. By proving new monogamy-of-entanglement bounds via SOS and leveraging them to analyze a matching-based algorithm, the authors provide the first non-trivial approximation guarantees for general qudit systems that surpass random assignment, with specific improvements for qubit systems and bounded-degree graphs.