updated 2025-08-17
Given a graph \(G(V,E,w)\) with vertex set \(V\), edge set \(E\), and nonnegative edge weights \(w\), the Quantum MaxCut (QMC) Hamiltonian is defined as:
\[H^{QMC}_G = \sum_{(i,j) \in E} w_{ij}\, h^{QMC}_{ij}\] \[h^{QMC}_{ij} :=\frac{1}{2}\left( I_i \otimes I_j - X_i \otimes X_j - Y_i \otimes Y_j - Z_i \otimes Z_j \right) = 2 \,w_{ij} \, \vert \psi^{-} \rangle_{ij} \langle \psi^{-} \vert_{ij}\,,\]where \(\vert \psi^{-} \rangle = \frac{1}{\sqrt{2}} (\vert 01\rangle - \vert 10\rangle),\) is the singlet state.
We present all known approximation algorithms for QMC. We concisely summarize techniques with the following notation and link to the appropriate Techniques.
| Reference | Value | Techniques |
|---|---|---|
| [GP19] | \(0.498\) | (Level-1 SoS | GP rounding) |
| [PT22] | \(1/2\) | (Level-2 SoS | Threshold: Cut state, GP rounding) |
| [HTPG24] | \(0.526\) | (Augmented SOCP | Threshold: Match state, Modified GP rounding) \(\cup\) (Augmented SOCP | Modified GP rounding ) |
| [AGM20] | \(0.531\) | (Forest-Match Bound, Cut Bound | Match State, Cut State, Forest State) |
| [PT21] | \(0.533\) | (Level-2 SoS | Threshold: Match State, GP rounding) \(\cup\) (Level-1 SoS | GP rounding) |
| [Lee22] | \(0.562\) | (Relaxed Level-2 SoS | GW rounding + AGM circuit) |
| [LP24] | \(0.595\) | (Level-2 SoS | GP rounding) \(\cup\) (Level-2 SoS Match bound | Match state) |
| [JKKSW24] | \(0.599\) | Improved analysis of [LP24] using improved level-2 SoS Match bound |
| [GSS25] | \(0.603\) | Improved analysis of [LP24] using level-13 SoS Match bound |
| [ALMPS25] | \(0.611\) | (Level-13 SoS | Threshold: Reweighted partial match state, GP rounding) \(\cup\) (Level-13 SoS | Match state) |
| Reference | Value | Techniques |
|---|---|---|
| [Kin23] | \(0.582\) | (Level-2 SoS | GP rounding + AGM circuit) |
| [GSS25] | \(0.61383\) | (Level-2 SoS | GP rounding + AGM circuit) \(\cup\) (Level-13 SoS \(13\)-Match bound | Match state) |
| Reference | Value | Techniques |
|---|---|---|
| [LP24] | \(0.606\) | (Level-2 SoS | GP rounding) \(\cup\) (Match bound | Match State) |
| [Kin23] | \(\sqrt{1/2} \approx 0.707\) | (EPR Level-2 SoS | Zero state + AGM circuit) |
| [ALMPS25] | \(\frac{1+\sqrt{5}}{2}\approx 0.809\) | (EPR fractional matching bound | AGM circuit) |
| [JN25] | \(\frac{1+\sqrt{5}}{2}\approx 0.809\) | (EPR bipartite matching bound | Match state) |
| [GSS25] | \(0.8162\) | (Level-2 SoS | Cut State + AGM circuit) |
We defined the QMC Hamiltonian with an overall normalization factor of \(1/2\). This is an arbitrary choice, and simply correspond to multiplicative scalings, which do not affect approximation ratios. Other choices have appeared in the literature; we list some pros and cons of each
| Coefficient | Pros | Cons |
|---|---|---|
| \(1/4\) | Ensures unit norm of each term | Excess fractions, computational basis states have different energy for QMC and MaxCut |
| \(1/2\) | Less fractions, computational basis state have same energy for QMC and MaxCut | Each term no longer has unit norm |
| \(1\) | Minimum fractions | No aligment with MaxCut, each term no longer has unit norm |
| \(1/||H||\) | Hamiltonian has unit norm | Excess fractions |
In certain cases, the identity term in Eq. (1) is dropped, making the Hamiltonian traceless. This changes the approximability of the Hamiltonian (see Sec 1.1 [GP19]).
In statistical mechanics, QMC is known as the antiferromagnetic Heisenberg model, and the problem is presented as:
Minimize
\[H = \sum_{(i,j) \in E} w_{ij} \left( X_i \otimes X_j + Y_i \otimes Y_j + Z_i \otimes Z_j \right) = \sum_{(i,j) \in E} w_{ij} \left( 2\left( S_i^+ S_j^- + S_i^- S_j^+ \right) + Z_i Z_j \right).\]Where
\[S_k^+ = \frac{X_k + i Y_k}{2}, \quad S_k^- = \frac{X_k - i Y_k}{2},\]are the canonical raising and lowering operators. Note that inverting the sign is accompanied by changing from maximization to minimization, yielding an equivalent problem. However, dropping the identity term does yield to a change in approximability. Thu, sometimes the identity term is reintroduced for consistency (with an appropriate negative sign).
The maximum value h^{QMC} can take on an edge is \(2\). Thus, an edge-wise application triangle inequality yields \(\|H^{QMC}_G\| \le \sum_{(i,j) \in E} w_{ij} \,\|h^{QMC}_{ij}\| = 2 W,\) where \(W\) is the total edge weight.
From Lemma 1 of [AGM20] we have if \(G(V,E,w)\) is a star graph then
\[\|H^{QMC}_G\| \le W+ \max_{j \,\sim\, i} w_{ij},\]where \(j \sim i\) denotes vertices adjacent to \(i\). In particular, if \(G\) is unweighted this simplifies to
\[\|H^{QMC}_G\| \le |E|+1.\]This can be strengthed by instead applying the triangle inequality vertex-wise
\begin{align}
|H^{QMC}G| &\le \frac{1}{2}\sum_i \left|\left| \sum{j \,\sim\, i} w_{ij} \, h^{QMC}{ij} \right|\right|
&\le \frac{1}{2}\sum_i \left(\sum{j \,\sim\, i} w_{ij} + \max_{j \,\sim\, i} w_{ij}\right)
&=W+\frac{1}{2}\sum_i \max_{j \,\sim\, i} w_{ij}.
\end{align}
Where in the first line we compensate for double-counting of edges with a factor of \(1/2\) and in the second line we apply Monogamy of Entanglement on a Star. For unweighted graphs this simplifies to \(\|H^{QMC}_G\| \le |E|+\frac{|V|}{2}\)
These bounds are of the form \(\|H^{QMC}_G\| \le W + a\,M\) for some \(a \ge 1\). It was shown in [LP24] to be valid for \(a=\frac{5}{4}\). This was later strengthened in [JKKSW24] to \(\frac{7}{6}\) and in [GSS25] to \(\frac{15}{14}\).
There have been two papers analyzing the average-case energy of algorithms for QMC on \(D\)-regular graphs. [MSS25], [KKZ24]. Both of these papers give variational algorithms for unweighted \(D\)-regular graphs with provable average-case energy guarantees in the infinite size limit. Among other results, both works show that quantum circuits can prepare states with energy within \(2\%\) error from the optimal for QMC on an infinite ring (also known as the 1D Heisenberg spin chain with periodic boundary conditions).