A classical algorithm moves the goalposts for “quantum advantage” in optimisation
Preprint, not yet peer-reviewed | Theory
It tests one of the few provable QAOA advantages over classical local algorithms and finds that, at equal depth, the advantage does not hold.
Our understanding
Imagine splitting a network into two teams so that as many connections as possible run between the teams. This classic puzzle is a favourite test for quantum computers. For one family of networks, a quantum method had given better guarantees than the classical methods of the same kind. Now a classical method does slightly better, as long as both look equally far around each point. On this test, the hoped-for quantum advantage is gone.
A few papers like this every Monday, free.
Free. Unsubscribe anytime. Privacy
The details
Key number: M66 ≥ 0.91271 at 99.99999 % confidence (one-sided bound from 10^7 samples at depth 32), valid for all 3-regular graphs of girth 66 or more.
What they did
Max-Cut asks how to split the nodes of a network into two groups so that as many links as possible run between the groups. On sparse networks where every node has exactly three neighbours and there are no short loops (“large girth”), nobody knows exactly what fraction of links can always be cut. In the limit of very large girth it lies between 0.912 and 0.92386. On such graphs every neighbourhood looks like the same tree, so an algorithm that only looks a fixed number of steps around each link (“local”, depth p) gives a guaranteed cut fraction for the whole family. In earlier work the quantum algorithm QAOA had given better guarantees of this kind than the best classical local algorithm from girth 16 on, which looked like a quantum advantage. The authors evaluate VIRAL (Variational Iterative Rotation Algorithm), a classical local algorithm they introduced earlier, on the depth-p tree for every even depth up to 32. Its guaranteed cut fraction beats the QAOA value at every depth from 4 to 18, by 0.005 to 0.011. QAOA values exist only up to depth 17, so depths 20 to 32 have no quantum comparison. The new values extend the range of girths covered from 36 to 66 and raise the best lower bound from 0.912 to 0.9127, at 99.99999 % statistical confidence.
Why it matters
At equal depth, a classical method gives better guarantees than QAOA on this benchmark family, and the authors say so plainly: “in this case, therefore, the advantage does not exist”, and “the quantum fluctuations of the QAOA are not a resource”. The classical bounds are constructive, and the algorithm runs in time linear in the number of links. The bound is statistical: the tree value is estimated from ten million random samples per depth, so M66 ≥ 0.9127 holds for all 3-regular graphs of girth 66 or more at 99.99999 % confidence, while the earlier QAOA values were computed exactly. VIRAL is the authors' own algorithm. This paper is a preprint, and the QAOA benchmark it compares against is cited as an arXiv preprint.
What is still open
Two, both posed by the authors: how much of the remaining gap to 0.92386 any local algorithm can close (the gains were still shrinking at depth 32), and whether the same picture holds for graphs with more neighbours per node and for Max-k-Cut with k ≥ 3.
The authors note: “the increments cVIRAL(p) − cVIRAL(p − 2) are still decreasing at p = 32 and the present data do not determine the limit p → ∞.” (arXiv:2610.17236v1, Discussion, p. 4 to 5)
