AnyonA classical algorithm moves the goalposts for "quantum advantage" in optimisation
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 looked better than every known classical method. 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.
Five of these every Monday, free.
The details
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 the best achievable fraction of cut links exactly; it is pinned 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 algorithms at moderate girth, which looked like a quantum advantage. The authors evaluate a classical local algorithm called VIRAL (Variational Iterative Rotation Algorithm) on the depth-p tree for every even depth up to 32. Its guaranteed cut fraction beats the QAOA value at every depth of 4 or more, by 0.005 to 0.011, extends the range of girths covered from 36 to 66, and raises the best proven lower bound from 0.912 to 0.9127.
Why it matters
QAOA is one of the most-cited candidates for a near-term quantum speed-up on optimisation problems. This result says that, at equal depth, a classical method does better 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 confidence level quoted in the abstract (99.99999 %) is a one-sided statistical bound per depth from ten million samples, not a statement about all graphs.
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.
