Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Technical Summary: Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Problem Statement
The paper addresses the problem of approximating the maximum energy, $\lambda_{\max}(H_G)$, of 2-local Hamiltonians defined on a graph $G(V, E, w)$. Specifically, it focuses on two distinct local terms:

1. Quantum MaxCut (QMC): Defined by the singlet state projector $h^{\text{QMC}}_{ij} = 2|\psi^-\rangle\langle\psi^-|$. The decision version of this problem is QMA-hard.
2. EPR Hamiltonian: Defined by the Bell state projector $h^{\text{EPR}}_{ij} = 2|\phi^+\rangle\langle\phi^+|$. While stoquastic and potentially easier than QMC, its polynomial-time solvability remains an open question.

The goal is to find efficiently computable lower bounds $\ell(G)$ on the maximum energy such that the approximation ratio $\alpha = \min_G \ell(G)/\lambda_{\max}(H_G)$ is maximized. Existing approaches rely on Semidefinite Programming (SDP) relaxations (specifically the quantum moment-SOS or Lasserre hierarchy) for upper bounds and various state preparation strategies (product states, matchings, variational circuits) for lower bounds. Prior to this work, the best known ratios were $\alpha \ge 0.603$ for QMC and $\alpha \ge (1+\sqrt{5})/4 \approx 0.809$ for EPR.

Methodology
The core innovation of the proposed algorithms is the construction of quantum states that partially entangle pairs of qubits associated with edges in a matching, while preserving the direction of their single-qubit Bloch vectors (up to a rescaling of magnitude). This technique allows the authors to interpolate smoothly between a product state and a fully entangled matching-based state using a tunable parameter $\theta$.

Key methodological components include:

• Preservation of Marginals: Unlike previous approaches that might destroy local properties when entangling, these algorithms ensure that the reduced density matrices of single qubits remain proportional to the original product state marginals (plus a scaled identity). This property is crucial for analytically bounding the energy of edges not in the matching in terms of the initial product state energy.
• EPR Algorithm (Fractional Matching): The algorithm utilizes a fractional matching $m$ to define a unitary circuit. It applies rotations $e^{i\gamma_{uv} P_u P_v}$ to the initial product state $|0\rangle^{\otimes n}$, where the rotation angles $\gamma_{uv}$ are determined by the fractional matching weights and a fixed parameter $\theta = \frac{1}{2}\ln(\phi)$ (where $\phi$ is the golden ratio).
• QMC Algorithm (Partial Matching): This approach combines two strategies:
  1. PMATCH: A subroutine that takes a product state derived from an SDP, identifies a maximum-weight integral matching on reweighted edges, and replaces the product states on matched edges with partially entangled 2-qubit states (parameterized by $\theta$) that satisfy the marginal preservation constraints. Unmatched qubits are also rescaled.
  2. Hybrid Selection: The final algorithm outputs the state with the higher energy between the standard MATCH algorithm (fully entangled matching) and the PMATCH algorithm (partially entangled).
• Re-weighting Strategy: For QMC, the algorithm selects a matching based on reweighted edges $w'_{ij} = w_{ij} \cdot (\sin \theta (1 - t_{ij}(1+\sin \theta)))^+$, where $t_{ij}$ is the inner product of the Bloch vectors from the product state. This effectively widens the search space beyond the standard maximum-weight matching.

Key Contributions and Results
The paper presents two main theorems establishing improved approximation ratios:

1. Theorem 1 (EPR): The proposed algorithm achieves an approximation ratio of $\alpha \ge \frac{1+\sqrt{5}}{4} \approx 0.809$.

   • Note: The authors acknowledge that this specific ratio was simultaneously and independently achieved by [JN25] using a different algorithm. However, they claim their algorithm and analysis are simpler. The analysis is shown to be optimal for certain graphs (e.g., single-edge graphs).

2. Theorem 2 (QMC): The proposed algorithm achieves an approximation ratio of $\alpha \ge 0.611$.

   • This result relies on the 13th level of the Lasserre hierarchy for the upper bound.
   • The authors note that if the upper bound constant $d$ in the monogamy-of-entanglement inequality is improved to 1 (as suggested by recent work [APS25] using separation oracles), the ratio improves to $\alpha \ge 0.614$ using only the 2nd level of the hierarchy.

Significance and Claims
The paper claims significance primarily through the introduction of the "partially entangled matching" technique. By interpolating between product and matching states while preserving single-qubit marginals, the authors can rigorously bound the energy of the entire system using the energy of the initial product state. This allows for a more nuanced optimization of the entanglement parameter $\theta$ to maximize the worst-case approximation ratio.

The work improves upon the state-of-the-art for QMC (raising the bound from 0.603 to 0.611) and provides a conceptually simpler derivation for the EPR bound. The authors emphasize that their analysis for EPR is tight for specific graph structures, while for QMC, the potential for further improvement exists if tighter upper bounds on $\lambda_{\max}(H_G)$ are incorporated. The algorithms are constructive, providing explicit quantum states (or circuits) that achieve these energy guarantees.