⚛️ quantum physics

Toward quantum scaling advantage in approximate optimization

This paper challenges recent claims of quantum scaling advantages in solving QUBO problems by demonstrating that the classical Simulated Bifurcation Machine achieves comparable or superior performance on larger instances, thereby closing the reported quantum-classical gap and suggesting that genuine quantum advantages are likely limited to specific sparse problem classes once hardware overheads are addressed.

Original authors: J. Pawłowski, P. Tarasiuk, J. Tuziemski, Ł. Pawela, B. Gardas

Published 2026-07-13

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: J. Pawłowski, P. Tarasiuk, J. Tuziemski, Ł. Pawela, B. Gardas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a giant, foggy mountain range. This is a classic puzzle for computers called an optimization problem. Recently, some researchers claimed that a special kind of "quantum" mountain climber (a quantum annealer) could find the bottom much faster than any classical computer as the mountains got bigger. They said this was a "quantum advantage."

But a new team of scientists decided to double-check this claim with a very different kind of climber: the Simulated Bifurcation Machine (SBM).

Think of the quantum climber as someone who uses "thermal fluctuations"—basically, they shake the ground to see if they can hop over a small hill. The SBM, however, is like a climber who uses chaos. Instead of shaking, they ride a wild, nonlinear wave that splits and jumps (bifurcates) through the terrain, guided by the laws of physics but running on a standard graphics card (GPU).

Here is what the authors found when they put these two climbers to the test:

1. The "Quantum Advantage" Might Be an Illusion
The previous study claimed the quantum climber was winning. However, the authors found that when you use the SBM, it runs just as fast, or even faster, than the quantum machine. In fact, for the problem sizes tested (up to about 1,322 logical variables), the SBM closed the gap completely. The "advantage" the quantum machine seemed to have disappeared once they accounted for all the time it takes to set up the run and read the results.

2. Small Mountains Lie
The authors argue that the previous study looked at mountains that were too small to tell the real story. It's like judging a marathon runner's speed based on a 100-meter dash; the start-up time matters too much. When the authors tested the SBM on much larger mountains—up to 38,320 variables (which would require a quantum computer with at least 1.5 × 10⁵ physical qubits to even attempt)—the classical SBM still held its own. The scaling remained robust, suggesting that for these specific types of problems, the quantum machine isn't currently beating the classical chaos machine.

3. The "Time" Trap
A big part of the confusion comes from how you measure time.

The Quantum Machine: The previous study used the "annealing time" (the time the machine says it spent climbing), which is a preset number like 14,100 µs for programming and 20.5 µs per sample for delays. They didn't count the time it took to talk to the machine or read the answer.
The SBM: The authors measured the actual time it took to get the answer, including all the "overhead" like moving data between the computer's brain and its graphics card.

When the authors included all the real-world time costs for the quantum machine, its speed advantage vanished. The "fast" scaling they saw earlier was mostly because they ignored the time it takes to get the machine ready.

4. Where Might the Quantum Machine Win?
The paper doesn't say quantum computers are useless. The authors suggest there is a specific, narrow path where quantum might win: 3D spin-glass problems.
In these specific, sparse puzzles, the quantum climber seems to find high-quality solutions incredibly fast (in the nanosecond scale) when looking only at the pure climbing time. However, the authors are careful to say this is only a potential advantage. Right now, the extra time needed to program and read the quantum machine wipes out that speed. They suggest that if future hardware can reduce those overheads, a genuine advantage might appear, but for now, it remains a "what if."

The Bottom Line
The authors conclude that for the specific problems they tested, the claim of a "quantum scaling advantage" is likely incorrect. The chaotic, classical SBM is a powerful contender that matches or beats the quantum machine when you count the whole race, not just the sprint. They suggest that to see a real win for quantum computers, we need to look at much larger problems and different types of puzzles, and we need to wait for hardware that can stop wasting time on setup and readout.

In short: The quantum climber isn't currently faster than the chaotic classical climber when you measure the whole trip. The "advantage" was likely just a trick of how the race was timed.

Technical Summary: Toward Quantum Scaling Advantage in Approximate Optimization

Problem Statement
The paper addresses a recent claim (Ref. [1]) that D-Wave quantum annealing exhibits a scaling advantage over classical heuristics when approximately solving Quadratic Unconstrained Binary Optimization (QUBO) problems. The authors argue that the reported advantage is not a genuine quantum effect but rather an artifact of methodological assumptions, specifically the use of "Quantum Annealing Correction" (QAC) and the definition of run-time metrics that exclude hardware overheads. The central question is whether a classical algorithm, sharing key operational features with quantum annealing (nearly parallel evolution and a defined relation between energy gap, run-time, and solution quality), can reproduce or surpass the reported scaling.

Methodology
The authors employ the Simulated Bifurcation Machine (SBM), a classical solver based on nonlinear Hamiltonian dynamics and chaotic behavior, rather than thermal fluctuations. The SBM is derived from a "dequantization" of quantum dynamics, utilizing a network of coupled nonlinear oscillators.

Algorithm: The SBM solves the Ising model (equivalent to QUBO) by evolving a system of variables $x_i, y_i$ governed by discretized equations of motion. The system undergoes a sequence of bifurcations driven by a linear schedule $p(t)$ , guiding the system toward low-energy states.
Metrics: The performance is evaluated using the Time-to- $\epsilon$ ( $TT_\epsilon$ ) metric, defined as the time required to find a solution within an optimality gap $\epsilon$ of the ground state with 99% probability. The authors analyze the median $TT_\epsilon$ ( $[TT_\epsilon]_{Med}$ ) across multiple instances.
Scaling Analysis: The study fits power-law relationships $[TT_\epsilon]_{Med} \propto N^\alpha$ to determine the scaling exponent $\alpha$ .
Experimental Scope:
1. Reproduction: The authors re-evaluate the specific "Sidon-28" instances from Ref. [1] (logical qubits $N \in [142, 1322]$ ) using the SBM on GPUs.
2. Extrapolation: They extend the analysis to much larger instances ( $N$ up to $\approx 3.8 \times 10^4$ ), a regime currently inaccessible to quantum annealers.
3. Alternative Problem Class: They investigate 3D spin-glass instances, a class where quantum annealers are theorized to perform well in the "fast annealing" regime.
Time Accounting: A critical component of the methodology is the rigorous distinction between:
- Measured time ( $t_{runtime}$ or $t_{tot}$ ): Includes all overhead (programming, readout, CPU-GPU communication, queuing).
- Set/Annealing time ( $\tau$ or $t_{GPU}$ ): The pure computation time, excluding overhead. The authors argue that comparing measured classical time against unmeasured quantum "set" time biases results in favor of quantum devices.

Key Contributions and Results

Closing the Quantum-Classical Gap: On the specific instances studied in Ref. [1], the GPU-based SBM achieves scaling exponents ( $\alpha$ ) comparable to, and in some regimes better than, the best QAC results. When overheads are included in the SBM's total run-time ( $t_{tot}$ ), it matches or surpasses the quantum annealer. When comparing pure compute times ( $t_{GPU}$ vs. $\tau$ ), the gap narrows further, suggesting the reported advantage is highly sensitive to overhead definitions.
Finite-Size Effects: The authors demonstrate that the scaling exponents are heavily influenced by overheads in small system sizes ( $N < 1500$ ). As the system size increases to $N \approx 3.8 \times 10^4$ , the impact of overhead vanishes, and the SBM exhibits robust polynomial scaling. This indicates that the small instances in Ref. [1] were insufficient to infer asymptotic behavior.
Refutation of Universal Advantage: The study concludes that for the QUBO problems and run-time accounting methods analyzed, current quantum annealers do not exhibit a clear scaling advantage over SBM-like solvers. The "advantage" reported previously is attributed to the exclusion of overheads and the specific constraints of QAC.
Identification of Potential Advantage Regimes: The paper identifies 3D spin-glass instances as a potential candidate for genuine quantum advantage. In this regime, when using the annealing time $\tau$ as a proxy for run-time, the quantum annealer shows superior scaling compared to SBM. However, the authors note that once realistic overheads (programming, readout) are included, this apparent advantage disappears for current hardware. They suggest that future devices with mitigated hardware overheads could potentially realize a genuine advantage in this specific sparse problem class.

Significance and Claims
The paper claims to provide a conceptual foundation for advancing toward genuine quantum advantage by shifting the baseline from thermal solvers (like PT-ICM) to quantum-inspired chaotic solvers (SBM).

Modest Claims: The authors do not claim that quantum annealing is useless; rather, they argue that claims of "quantum advantage" must be validated against steadily improving classical algorithms and must account for all operational overheads.
Reinterpretation of Data: They posit that the observed scaling in Ref. [1] cannot be uniquely interpreted as a quantum effect, as it can be reproduced by a classical system sharing key dynamical features with quantum annealing.
Future Outlook: The paper suggests that a genuine scaling advantage may only be achievable for specific, sparse problem classes (like 3D spin glasses) and only once hardware-level run-time limitations (overheads) are significantly mitigated. Until then, current-generation quantum processing units (QPUs) are unlikely to outperform classical solvers in approximate discrete optimization under rigorous time accounting.

More like this