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
HG=i<j∑wij(I−SWAPij),OPT(G)=λmax(HG).
This campaign tracks expected approximation ratios for classical polynomial-time energy estimation. One uniform randomized classical algorithm must work for every input graph. For each fixed G, let R be the algorithm's internal fair random bits, and let v(G,R) be its nonnegative rational output. A ratio α requires
0≤v(G,R)≤OPT(G)for every random outcome R,ER[v(G,R)]≥αOPT(G).
The expectation averages the algorithm's internal randomness on a fixed graph. Its running time is bounded by a polynomial on every run. Higher ratios are better.