Quantum annealing shows a scaling edge on spin glasses

The argument that a quantum computer should be faster than a classical one for any useful task has, until recently, been an argument about asymptotics. A theorem says that, with enough qubits and low enough error, factoring will be fast and linear algebra will be fast. Engineering reality has not cooperated: the machines that exist today are small and noisy, and the benchmarks that mattered most were demonstrations of sampling speed, not solutions to problems anyone wants solved. A paper posted to arXiv on 15 January 2024 by a D-Wave team, ‘Scaling Advantage in Approximate Optimization with Quantum Annealing’, reports something narrower and more concrete: on one well-defined family of optimization problems, the quantum machine gets better, relative to the best classical method, as the problem gets bigger.

The test bed is a 2D spin glass, a lattice of spins with specified interaction signs, whose ground state is a hard optimization problem. The team ran the Advantage 4.1 processor, a Pegasus-graph chip with thousands of superconducting qubits, on a family of such problems with high-precision spin-spin couplings. The comparison classical method was parallel tempering with isoenergetic cluster moves, the strongest known heuristic for this problem class. The quantity measured is time to a solution of fixed quality, as the lattice grows. Without correction, the annealer does not obviously beat the heuristic. With a technique called quantum annealing correction switched on, it does: the time-to-solution grows more slowly with problem size on the quantum device, and the advantage widens as the problem is scaled up.

Quantum annealing correction is the detail that makes the result credible. It is an embedding of a bit-flip error-correcting code, with energy penalties attached to the encoded couplings, that suppresses the thermal noise which otherwise limits a noisy annealer’s answer quality. The result is therefore not a raw qubit count story. It is a control story: the same hardware, run with noise protection, exhibits a scaling advantage that the unprotected run does not. That matters because the most common criticism of annealing-based quantum computing has been that it is a specialized machine whose results can always be simulated by Monte Carlo; the paper’s claim is that, on this problem family, the protected annealer out-scales the Monte Carlo method.

The honest scope is the first thing to read. This is approximate optimization, not exact solutions, and it is one problem family on one hardware platform. Spin glasses are deliberately chosen because they are hard and because good classical heuristics exist; the advantage reported is relative to that heuristic, not to the rest of computing. The team is careful to say that the scaling edge is shown for the 2D problems studied, and that whether it survives on 3D lattices or on industrially shaped problems is a separate question.

For a field that has spent a decade arguing about whether its machines do anything classical cannot, a scaling advantage of this kind is the shape of answer the argument needed. It does not demonstrate fault tolerance, it does not factor numbers, and it does not put a quantum algorithm on your desktop next year. It does show, on real hardware and against a serious classical opponent, that a quantum machine’s relative performance improves as problems grow. That is the property that asymptotic theorems promise, and it is the property that had been missing from the experimental record. The next questions are whether the correction technique generalizes and whether the classical heuristic can be improved, both of which will now be tried.