Classical Bifurcation Solver Closes Quantum Annealing Gap

Claims of quantum scaling advantage in approximate optimization depend as much on the accounting model as on the solver. The paper revisits a recent report that D-Wave quantum annealing scales better than classical methods on quantum-annealing-correction-type QUBO instances. Its central point is narrower and more useful: when the comparison is made against a quantum-inspired simulated bifurcation machine, and when runtime overheads and larger instance sizes are included, the reported quantum-classical gap largely disappears.

Core Contribution

The contribution is a direct challenge to a specific scaling claim, not a new universal optimizer. The authors compare D-Wave Advantage 4.1 against a simulated bifurcation machine, a nonlinear dynamical-system solver derived from quantum dynamics but run classically on GPUs. SBM has two properties that make it a more serious baseline than many generic classical solvers: it evolves many variables in a near-parallel manner, and it has a controllable relation between energy gap, runtime, and target solution quality.

That choice matters because the earlier quantum-advantage claim was based on small instances and a particular runtime proxy. The authors argue that those instances are too small to support asymptotic conclusions. Extending the scaling analysis changes the interpretation: SBM obtains comparable or better time-to-target behavior under the studied run-time definitions, so the evidence no longer supports a clear scaling advantage for current quantum annealers on this QUBO family.

Technical Approach

The benchmark is framed around time-to-$\epsilon$, written as $[\mathrm{TTe}]_{\mathrm{Med}}$: the median time needed to reach a solution within a specified relative error threshold. The paper varies $\epsilon$ rather than treating success as a single exact optimum event, which is appropriate for approximate optimization but also makes the thresholds part of the experimental claim.

For the quantum annealer, the authors separate several timing notions: annealing time per sample $\tau$, QPU access time including programming, postprocessing, annealing, readout, and thermalization, and a broader external runtime that also includes queueing and communication overhead. They emphasize that $\tau$ is the only timing quantity easily varied without direct hardware access, but it omits much of the real operational cost. For SBM, the analogous split is between GPU compute-loop time and total time including CPU-to-GPU transfer. A key methodological point is that SBM integrates all samples in parallel, while quantum annealing processes samples sequentially under the accounting used here.

Results and Analysis

On the S28 QAC instances, the visible supplementary scaling plots cover $\epsilon = 0.75\%$, $1.00\%$, $1.10\%$, and $1.25\%$. The authors report that D-Wave scaling exponents become sensitive to which runtime is counted, while SBM scaling remains more stable across timing definitions. The practical reading is that the quantum result is not just a hardware-vs-software comparison; it is a comparison between different definitions of what a solver run costs.

The larger-instance analysis is the more damaging part for the prior claim. The authors state that for current annealers, $\tau$ becomes small compared with the growth in problem time, making fitted exponents statistically unreliable for the small instances previously studied. Under the favorable assumption $C \gg t(N_{\mathrm{final}})-t(N_{\mathrm{initial}})$, the annealer appears to scale cleanly only because the chosen timing proxy hides the part that should grow with instance size. Under the same scrutiny, a single-GPU SBM does not show a quantum disadvantage.

The paper does not dismiss future quantum scaling advantage. It identifies sparse problem classes, especially 3D spin glasses, as more plausible targets once hardware overheads fall. The supplementary 3D spin-glass plots span instance sizes from 432 to 5374 and thresholds from $\epsilon = 0.50\%$ to $1.10\%$. At $\epsilon = 0.50\%$, the largest instances cannot be reliably minimized by either solver and the fitted exponents rise quickly. Around $\epsilon = 1.10\%$, both SBM and D-Wave keep power-law behavior, with the annealer’s exponent close to its $\epsilon = 1.00\%$ value while SBM’s optimized annealing time decreases. Above that, the task becomes too easy to reveal meaningful scaling.

Caveats

The evidence is a strong critique of the earlier quantum-advantage interpretation, but not a final statement about quantum annealing in general. The conclusion is conditional on QAC-type QUBOs, the selected approximation thresholds, the available D-Wave Advantage 4.1 hardware, and the runtime accounting used in the experiments. The forward-looking claim about sparse spin glasses is plausible but remains a path for future devices, not a demonstrated advantage here.