QAOA and Quantum Optimization

The poster problem for quantum optimisation is MaxCut. Take a graph — vertices, edges — and paint every vertex one of two colours. An edge is "cut" when its endpoints get different colours, and the task is to choose the colouring that cuts the most edges. It looks like a puzzle and it is a monster: MaxCut is NP-hard, it shows up wherever something must be split into two groups with maximum disagreement across the boundary — circuit layout, spin glasses, clustering — and nobody expects any algorithm, classical or quantum, to solve every instance efficiently.

The encoding into quantum mechanics is almost embarrassingly direct. Give each vertex a qubit and read colour off the computational basis: |0⟩ is one side of the cut, |1⟩ the other. For an edge (i, j), the operator (1 − Z_iZ_j)/2 evaluates to 1 when the endpoints differ and 0 when they agree — check it on the four basis combinations, it is a one-line calculation. Summing over the edges gives the cost Hamiltonian C = Σ_{(i,j)} (1 − Z_iZ_j)/2, whose eigenvalue on any basis state is exactly the number of edges that colouring cuts. The best cut is the highest-eigenvalue eigenstate.

Pause on a structural point that separates this from the VQE chemistry problem you already know. C is diagonal in the computational basis. Every eigenstate is a plain classical bit string; the answer we want is not an entangled state, it is a colouring you could write on paper. Nobody needs a quantum computer to REPRESENT a cut, or to evaluate one — counting cut edges is instant. The only possible quantum contribution is to the SEARCH: arranging interference so that a measurement lands on a good bit string more often than blind luck would.

One more piece of vocabulary and the classical bar it sets. An algorithm has approximation ratio α if it always delivers at least α times the optimal cut. Painting vertices at random cuts half the edges on average, which already guarantees ratio 1/2 on any graph. The classical algorithm to beat is Goemans–Williamson (1995), a semidefinite-programming rounding scheme with a proven ratio of about 0.878 on every graph — and under a standard complexity conjecture, doing better than that in the worst case is NP-hard for any algorithm whatsoever, quantum ones included. Whatever QAOA is for, it is not for breaking that barrier.