updated 2025-08-17
Given a graph \(G(V,E,w)\) with vertex set \(V\), edge set \(E\), and nonnegative edge weights \(w\), the XY Hamiltonian is defined as:
\[H^{XY}_G = \sum_{(i,j) \in E} w_{ij}\, h^{XY}_{ij}\] \[h^{XY}_{ij} :=\frac{1}{2}\left( I_i \otimes I_j - X_i \otimes X_j - Y_i \otimes Y_j \right)\]We present all known approximation algorithms for EPR. We concisely summarize techniques with the following notation and link to the appropriate Techniques.
| Reference | Value | Techniques |
|---|---|---|
| [GP19] | \(0.649\) | (Level-1 SoS | GP rounding) |
| [APS25] | \(0.674\) | (Cut Bounds, Match Bound | Cut State, Match State) |
We defined the XY Hamiltonian based on the original definition by [GP19] with an overall normalization factor of \(1/2\). This was originally chosen to match the energy of computational basis states between QMC, XY, and MaxCut. We are unaware of any other conventions currently used in the literature.
In statistical mechanics, XY is known as the antiferromagnetic XY model, and the problem is presented as:
Minimize \begin{align} H &= \sum_{(i,j) \in E} w_{ij} \left(X_i \otimes X_j + Y_i \otimes Y_j \right) \, \end{align}
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. Thus, sometimes the identity term is reintroduced for consistency (with an appropriate negative sign).
Similar upper bounds presented in \(QMC\) hold for XY, as demonstrated in ALMPS25.
There have been two papers analyzing the average-case energy of algorithms for XY 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.