Quantum Max-Cut

Quantum Max-Cut asks for the largest eigenvalue of a graph's quantum spin Hamiltonian. For a graph $G$ with nonnegative rational edge weights, write

$$H_G=\sum_{i<j}w_{ij}(I-\mathrm{SWAP}_{ij}),\qquad\mathrm{OPT}(G)=\lambda_{\max}(H_G).$$

This campaign formalizes classical polynomial-time algorithms that estimate this optimal energy. At ratio $\alpha$, the goal is one randomized classical algorithm which, for every input graph, outputs a number $v$ satisfying

$$0\le v\le\mathrm{OPT}(G),\qquad\mathbb E[v]\ge\alpha\,\mathrm{OPT}(G).$$

The upper bound holds for every random outcome; the approximation ratio is guaranteed in expectation. The optimum includes entangled quantum states. The algorithm returns a classical numerical estimate and requires no physical state preparation. Higher approximation ratios are better.

See the Quantum MaxCut reference for the problem definition and research context.