Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Toward quantum scaling advantage in approximate optimization

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read A GPU-based classical solver matches or beats the quantum annealer's time-to-epsilon scaling on Sidon-28 QUBO instances, so the reported quantum scaling advantage does not survive a different classical baseline.

desk verdict A credible SBM benchmark closes the reported quantum annealing scaling gap on the original instances, but the large-instance extrapolation rests on ground-state certifications and unpublished instances that need scrutiny. read the letter →

arxiv 2505.22514 v2 pith:V2VIJTN6 submitted 2025-05-28 quant-ph physics.comp-ph

classification quant-phphysics.comp-ph
keywords quantumannealingQUBOsimulatedbifurcationmachinetime-to-epsilonscalingadvantageSidon-28instancesGPUcomputing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tests a recent claim that quantum annealing achieves a scaling advantage in approximate optimization of QUBO problems. By replacing the original classical baseline (parallel tempering) with a GPU-implemented simulated bifurcation machine, the authors find that the classical solver matches or outperforms the quantum annealer's time-to-epsilon on the same Sidon-28 instances. They argue that the small instance sizes used previously (up to about 1300 variables) cannot support asymptotic conclusions, because the measured scaling exponent depends strongly on how runtime is counted. Extending to instances with up to 38,320 variables, they report classical scaling exponents around 1.5-1.7 that are stable across the optimality gaps tested. If accepted, the conclusion is that current-generation quantum annealers are unlikely to show a clear, operationally meaningful scaling advantage on this class of problems; the paper points to sparse problem classes as the plausible terrain for future quantum advantage once hardware overheads shrink.

What carries the argument

The yardstick is the time-to-epsilon metric, $\mathrm{TT}_\varepsilon = t_f \log(0.01)/\log(1 - p_{E \le E_0+\varepsilon|E_0|})$ (Eq. 1), which converts a solver's measured running time and success probability into a single effective time to reach a given relative optimality gap $\varepsilon$. The contender is the simulated bifurcation machine, a nonlinear Hamiltonian dynamical system whose equations (Eqs. 2-3) couple variables through Ising interactions, drive the system through a bifurcation point with a linear schedule $a(t)=t/T$, and impose an inelastic wall at $|q_i|=1$; a time-dependent threshold discretizes the interaction to the sign of the variable. Chaotic sensitivity lets many replicas run in parallel on GPUs, and the hyperparameters — the number of steps $N_s$ and number of replicas $N_r$ — are optimized per instance size. This TT-yardstick is used to compare SBM, PT-ICM, and two quantum-annealer sampling methods on identical instances.

What would settle it

Recompute the large-instance TT-$\varepsilon$ curves with independently certified ground-state energies (for example, by an exact branch-and-bound solver or by matching lower bounds), and also recompute the small-instance comparison with a runtime definition that includes all quantum-device programming and readout times; if either change makes the quantum-annealing exponent smaller than SBM's, the paper's conclusion that current quantum annealers show no clear advantage would be overturned.

Watch

Extended reading notes

Core claim

The paper's central claim is that the time-to-epsilon scaling exponent of the simulated bifurcation machine on the exact Sidon-28 instances used in Ref. [1] is comparable to or smaller than the exponent of quantum annealing with error correction (QAC) for optimality gaps 0.75% to 1.25%, even when all CPU-GPU communication overhead is included. It further claims that exponents fitted to the small instance set are not reliable indicators of asymptotic behavior; the same SBM data, fit over $N = 2380$ to $38320$, gives exponents between $1.5$ and $1.7$ that vary only weakly with $\varepsilon$ and with runtime accounting. The conclusion the authors draw is that the previously reported quantum-classical gap is an artifact of the chosen classical baseline and of finite-size effects, and that current QPUs do not exhibit genuine supremacy in approximate discrete optimization under operationally meaningful conditions.

Load-bearing premise

The large-instance scaling exponents that anchor the asymptotic conclusion assume that the Sidon-28 instances with $L=20$ to $L=80$ are drawn from the same distribution as the original instances and that the reported ground-state energies are exact up to $N=38320$.

Editorial extensions

If this is right

  • SBM with one GPU and total runtime matches or beats QAC for all tested optimality gaps on the small Sidon-28 instances, so the reported quantum advantage does not hold against a different classical baseline.
  • Scaling exponents from $N \le 1322$ are sensitive to whether runtime is counted as wall-clock or pure GPU time, so small instances cannot anchor asymptotic claims about quantum advantage.
  • At larger sizes ($N = 2380$ to $38320$), SBM's time-to-epsilon scaling lies in $1.5 < \alpha < 1.7$ and is nearly independent of $\varepsilon$ in the tested range, providing a stable classical baseline for future quantum-device comparisons.
  • Current-generation quantum annealers are therefore unlikely to demonstrate a clear scaling advantage on QAC-type QUBO problems under the time-to-epsilon accounting used here.
  • Sparse problem classes are identified as the promising place to seek genuine future quantum advantage, conditional on reduced hardware overheads.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The large-instance result is only as strong as the ground-state certification: if the reported $E_0$ values for $N$ up to $38320$ are not actually exact, the fitted exponents could be systematically too low and the asymptotic conclusion would weaken.
  • The runtime-accounting sensitivity shown here suggests a simple test for future advantage claims: report total wall-clock time including all solver overheads, and compare against at least one chaotic-dynamics solver and one thermal solver.
  • Because SBM exponents improve with more GPUs and with newer classical hardware, the classical baseline will keep moving; quantum advantage claims should specify the classical hardware generation, as happened with random-circuit sampling.
  • The sparse-instance, large-$\varepsilon$ window that the paper mentions as favorable to QPUs is also one where SBM needs no modification, so the prediction of future quantum advantage there is conditional on hardware-overhead reductions the paper does not quantify.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The manuscript reassesses the recent quantum-annealing scaling-advantage claim of Munoz-Bauza and Lidar by benchmarking a GPU implementation of the Simulated Bifurcation Machine (SBM) on the same Sidon-28 QUBO instances (N=142 to N=1322). Using the time-to-epsilon metric of Ref. [1], it reports SBM scaling exponents comparable to or lower than D-Wave QAC and PT-ICM, and it argues that the small-instance exponents are unstable with respect to runtime accounting and problem size. The paper then presents new large-instance results (N=2380 to N=38320) with scaling exponents alpha approximately 1.5 to 1.7 and concludes that current-generation quantum annealers are unlikely to demonstrate true supremacy in approximate optimization under operationally meaningful conditions.

Significance. If correct, the paper would substantially qualify a published PRL advantage claim and would strengthen the case that classical GPU-based chaotic solvers provide a competitive benchmark for approximate QUBO optimization. The small-instance benchmark has clear strengths: it uses instances from the original public dataset, 100 independent runs per instance, bootstrap error bars, and a transparent distinction between total runtime and pure GPU runtime. The large-instance extrapolation, however, is the load-bearing component of the asymptotic conclusion, and its current presentation does not fully support it. The manuscript also makes a useful methodological point that scaling exponents obtained from small sizes depend strongly on runtime accounting and on the choice of epsilon, which deserves to be preserved in any revised version.

major comments (3)
  1. [Supplemental Material, 'Scaling in large instance regime'; Fig. S2; Eq. (1)] The asymptotic claim alpha approximately 1.5-1.7 rests on TT_epsilon values computed with Eq. (1) using E0 'certified by Gurobi solver', but the paper provides no optimality certificates, solver time limits, or optimality gaps for the L=20 to L=80 instances (N up to 38320), and it does not release these instances or a generation script. If E0 is only an upper bound, then p(E <= E0 + epsilon|E0|) is overestimated and TT_epsilon is underestimated, which can artificially lower the fitted alpha and invalidate the robustness conclusion. In addition, the SM says 'we consider the same Sidon-28 instances' but immediately describes '10 random instances' per size, so the relationship to the original Ref. [1] instances is unclear. The authors should either certify exact optimality for the large instances and make the instances and certificates available, or explicitly restrict the asymptotic claim to the N <= 1322 regime.
  2. [Fig. 1, Fig. S2, and Methods] The SBM hyperparameters N_s and N_r are optimized on the same instances used to produce the scaling exponents, with no cross-validation or hold-out set. Because TT_epsilon is minimized over (N_s, N_r) separately for each instance size and each epsilon value, the reported exponents reflect in-sample tuning, and the degree of overfitting is unknown. Before accepting the 'closing the gap' claim as evidence of a general classical scaling property, the authors should report a validation split, nested optimization, or some other guard against selection bias in the hyperparameters.
  3. [Fig. S2 and accompanying SM text] The large-instance scaling is based on only 10 instances per size, yet the paper reports no per-size spread, confidence intervals, or instance-level TT_epsilon values for this regime, in contrast to the small-instance analysis where bootstrap errors are shown. With ten samples, the median and the fitted exponent are sensitive to a few outlier instances; the authors should report per-size distributions or bootstrap intervals for [TT_epsilon]_Med in Fig. S2 before describing the large-instance scaling as 'robust'.
minor comments (4)
  1. [Abstract and Discussion] The phrase 'true supremacy' is stronger than the evidence presented; a narrower statement about scaling advantage on Sidon-28-type QUBO instances would better match the scope of the benchmark.
  2. [Eq. (3) and Methods] The coefficient 0.7 in Delta(t) = 0.7 t/T is introduced without justification or sensitivity analysis; a brief discussion of its role or a reference to the quantized-SBM literature would help.
  3. [Supplemental Material] There are typographical errors ('Advantege series', 'problem siszes' in Ref. [30]) and the statement that the large instances are 'the same Sidon-28 instances' should be reworded, since new random draws are described.
  4. [Data availability] The manuscript does not state where the code, the large-instance generation script, or the instance files will be deposited; a data availability statement is needed, especially since the large-instance results are not derived from the public Harvard Dataverse dataset.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: empirical benchmark against external instances with transparent metrics.

full rationale

The paper's central claim is an empirical benchmark, not a derivation from first principles. SBM is a published algorithm (Goto et al.) with a documented discretization modification; the benchmark instances are the external Sidon-28 instances from Ref. [1] (Harvard Dataverse) for the small-size comparison, and new draws of the same distribution for large sizes. TT-epsilon is defined exactly as in Ref. [1], and E0 is certified by the external Gurobi solver; no target quantity is folded into the definition of the solver or the metric. The SBM hyperparameters (N_s, N_r) are optimized per instance size against TT-epsilon, but this is standard and transparent benchmark tuning, not a fitted quantity renamed as a prediction; the reported scaling exponents are least-squares fits to the measured medians, not predictions derived from those fits. Citations to the authors' own prior work (VeloxQ, GPU implementations) and to Goto et al. are background and do not carry the argument. Concerns about whether large-instance E0 values are truly certified, or whether the large instances match the original distribution, are correctness and verifiability risks, not circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities; it uses an existing classical solver (SBM) with a previously published ternary discretization. The main free content is benchmark tuning (Ns, Nr) and the choice of runtime accounting, along with inherited algorithm coefficients.

free parameters (4)
  • Ns (number of SBM steps) = Optimized per instance size and epsilon, shown in Fig. 1 bottom rows (up to ~2000 for large N)
    Optimized to minimize [TT-epsilon]Med for each N and epsilon; affects the reported runtime and scaling exponent.
  • Nr (number of replicas) = Optimized per instance size and epsilon, up to 2^12 for small N
    Optimized alongside Ns; more replicas improve success probability at the cost of runtime.
  • c0 = 0.7 a0 / (sigma sqrt(N)) = 0.7 / (sigma sqrt(N)) with a0 = 1
    Standard SBM coupling strength inherited from Goto et al.; contains a hand-chosen coefficient 0.7.
  • Ternary threshold coefficient in Delta(t) = 0.7 t / T = 0.7
    Chosen threshold slope for the ternary discretization (ref. [33]); not derived from first principles in this paper.
assumptions (4)
  • domain assumption The ground-state energies E0 are certified exactly by Gurobi for all instances, including N up to 38320.
    Eq. (1) defines TT-epsilon relative to E0; the paper refers to Gurobi certification but gives no details for large instances.
  • domain assumption The time-to-epsilon metric in Eq. (1) is an operationally meaningful measure of approximation quality for comparing solvers.
    The whole benchmark depends on this metric; the paper critiques D-Wave's use of fixed input time tau but retains TT-epsilon as the comparison quantity.
  • domain assumption SBM's chaotic dynamics with the given equations and hyperparameters explores low-energy configurations as claimed.
    The solver's success probability underlies all probability estimates; the paper validates empirically but does not prove convergence.
  • domain assumption The larger Sidon-28 instances (L=20..80) are generated from the same distribution as the original Ref. [1] instances and are representative for asymptotic scaling.
    Only 10 instances per size are used; generation details are not fully specified in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Toward quantum scaling advantage in approximate optimization." pith.science (2026). https://pith.science/paper/V2VIJTN6

@misc{pith2026250522514,
  author       = {Pith},
  title        = {Pith review of: Toward quantum scaling advantage in approximate optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V2VIJTN6}},
  note         = {Machine review of arXiv:2505.22514}
}
read the original abstract

In a recent Letter [H. Munoz-Bauza and D. Lidar, Phys. Rev. Lett. 134, 160601 (2025)], quantum annealing was reported to exhibit a scaling advantage in approximately solving quadratic unconstrained binary optimization (QUBO) problems. Here, we revisit these findings by employing the simulated bifurcation machine (SBM), a nonlinear dynamical system that exploits chaotic behavior rather than thermal fluctuations. Our approach originates from quantum dynamics and shares key operational features with quantum annealing: (i) nearly parallel evolution and (ii) a well-defined relation between the energy gap, run-time, and solution quality. We obtain comparable or superior scaling, closing the reported quantum-classical gap. We further show that the small instances studied previously are insufficient to infer asymptotic behavior. Extending the analysis to larger problems reveals robust classical performance, indicating that current quantum annealers are unlikely to exhibit a clear scaling advantage over SBM-like solvers on quantum-annealing-correction-type QUBO problems under the run-time accounting studied here. Finally, we identify sparse problem classes where future quantum devices could achieve a genuine scaling advantage, once hardware overheads are mitigated.

Figures

Figures reproduced from arXiv: 2505.22514 by the authors.

Figure 1
Figure 1. FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Thermodynamic significance of QUBO encoding on quantum annealers

    quant-ph 2026-01 conditional novelty 6.0 of 10

    Penalty weights in a QUBO encoding act as thermodynamic control knobs, changing both solver success and irreversibility on a quantum annealer.

  2. EMU circulation planning for Silesian Railways: case study and a quantum approach

    quant-ph 2025-12 conditional novelty 4.0 of 10

    Classical ILP solves daily Silesian EMU circulation for 404 trips, while the direct QUBO reformulation becomes impractical beyond roughly 78 trips.

Reference graph

Works this paper leans on

33 extracted references · 12 canonical work pages · cited by 2 Pith papers

  1. [1]

    Munoz-Bauza and D

    H. Munoz-Bauza and D. Lidar, Scaling advantage in ap- proximate optimization with quantum annealing, Phys. Rev. Lett.134, 160601 (2025)

  2. [2]

    A. W. Harrow and A. Montanaro, Quantum computa- tional supremacy, Nature549, 203 (2017)

  3. [3]

    Boixo, S

    S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near- term devices, Nature Physics14, 595 (2018)

  4. [4]

    Morvan, B

    A. Morvan, B. Villalonga, X. Mi, S. Mandr` a, A. Bengts- son, P. V. Klimov, Z. Chen, S. Hong, C. Erickson, I. K. Drozdov, J. Chau, G. Laun, R. Movassagh, A. Asfaw, L. T. A. N. Brand˜ ao,et al., Phase transitions in random circuit sampling, Nature634, 328 (2024)

  5. [5]

    Y. Zhou, E. M. Stoudenmire, and X. Waintal, What lim- its the simulation of quantum computers?, Phys. Rev. X 10, 041038 (2020)

  6. [6]

    Tanggara, M

    A. Tanggara, M. Gu, and K. Bharti, Classically spoofing system linear cross entropy score benchmarking (2024), arXiv:2405.00789 [quant-ph]

  7. [7]

    Aharonov, X

    D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazi- rani, A polynomial-time classical algorithm for noisy ran- dom circuit sampling, inProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC ’23 (ACM, 2023)

  8. [8]

    Tindall, M

    J. Tindall, M. Fishman, E. M. Stoudenmire, and D. Sels, Efficient tensor network simulation of IBM’s Eagle kicked Ising experiment, PRX Quantum5, 010308 (2024)

Show all 33 references
  1. [9]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins,et al., Quantum supremacy using a pro- grammable superconducting processor, Nature574, 505 (2019)

  2. [10]

    Y. A. Liu, X. L. Liu, F. N. Li, H. Fu, Y. Yang, J. Song, P. Zhao, Z. Wang, D. Peng, H. Chen, C. Guo, H. Huang, W. Wu, and D. Chen, Closing the ”quantum supremacy” gap: achieving real-time simulation of a random quan- tum circuit using a new Sunway supercomputer, inPro- ceeding...

  3. [11]

    F. Pan, K. Chen, and P. Zhang, Solving the sampling problem of the Sycamore quantum circuits, Phys. Rev. Lett.129, 090502 (2022)

  4. [12]

    Preskill, Quantum Computing in the NISQ era and beyond, Quantum2, 79 (2018)

    J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum2, 79 (2018)

  5. [13]

    A. D. King, A. Nocera, M. M. Rams, J. Dziarmaga, R. Wiersema, W. Bernoudy, J. Raymond, N. Kaushal, N. Heinsdorf, R. Harris, K. Boothby, F. Altomare, M. Asad, A. J. Berkley, M. Boschnak,et al., Beyond- classical computation in quantum simulation, Science 388, 199 (2025)

  6. [15]

    Mauron and G

    L. Mauron and G. Carleo, Challenging the quantum ad- vantage frontier with large-scale classical simulations of annealing dynamics (2025), arXiv:2503.08247 [quant-ph]

  7. [16]

    A. D. King, A. Nocera, M. M. Rams, J. Dziarmaga, J. Raymond, N. Kaushal, A. W. Sandvik, G. Al- varez, J. Carrasquilla, M. Franz, and M. H. Amin, Comment on: ”dynamics of disordered quantum sys- tems with two- and three-dimensional tensor networks” arXiv:2503.05693 (2025), arXi...

  8. [17]

    Glover, G

    F. Glover, G. Kochenberger, R. Hennig, and Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, Annals of Operations Research 314, 141 (2022)

  9. [18]

    Boothby, A

    K. Boothby, A. D. King, and J. Raymond, Zephyr topol- ogy of D-Wave quantum processors (2021), accessed: 2025-01-31

  10. [19]

    Kochenberger, J.-K

    G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. L¨ u, H. Wang, and Y. Wang, The unconstrained binary quadratic programming problem: a survey, Journal of Combinatorial Optimization28, 58 (2014)

  11. [20]

    Z. Zhu, A. J. Ochoa, and H. G. Katzgraber, Efficient cluster algorithm for spin glasses in any space dimension, Phys. Rev. Lett.115, 077201 (2015)

  12. [21]

    Delahaye, S

    D. Delahaye, S. Chaimatanan, and M. Mongeau, Simu- lated annealing: From basics to applications, inHand- book of Metaheuristics, edited by M. Gendreau and J.-Y. Potvin (Springer International Publishing, Cham, 2019) pp. 1–35

  13. [22]

    H. Goto, K. Tatsumura, and A. R. Dixon, Combina- torial optimization by simulating adiabatic bifurcations in nonlinear hamiltonian systems, Science Advances5, eaav2372 (2019)

  14. [23]

    H. Goto, K. Endo, M. Suzuki, Y. Sakai, and Taro et al., High-performance combinatorial optimization based on classical mechanics, Science Advances7, eabe7953 (2021)

  15. [24]

    Goto, Bifurcation-based adiabatic quantum computa- tion with a nonlinear oscillator network, Scientific Re- ports6, 21686 (2016)

    H. Goto, Bifurcation-based adiabatic quantum computa- tion with a nonlinear oscillator network, Scientific Re- ports6, 21686 (2016)

  16. [25]

    A. M. Dziubyna, T. ´Smierzchalski, B. Gardas, M. M. Rams, and M. Mohseni, Limitations of tensor-network approaches for optimization and sampling: A compari- son to quantum and classical Ising machines, Phys. Rev. Appl.23, 054049 (2025)

  17. [26]

    K. L. Pudenz, T. Albash, and D. A. Lidar, Error- corrected quantum annealing with hundreds of qubits, Nature Communications5, 3243 (2014)

  18. [27]

    Munoz Bauza and D

    H. Munoz Bauza and D. Lidar, Scaling Advantage in Approximate Optimization with Quantum Annealing - Spin-Glass Instances (2025)

  19. [28]

    Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2024)

  20. [29]

    Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 10.3389/fphy.2014.00005 (2014)

    A. Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 10.3389/fphy.2014.00005 (2014)

  21. [30]

    See Supplemental Material for the discussion of multi- GPU SBM results, as well as the scaling properties in the regime of large problem siszes

  22. [31]

    J. Hou, A. Barzegar, and H. G. Katzgraber, Direct com- parison of stochastic driven nonlinear dynamical systems for combinatorial optimization (2025), arXiv:2503.15427 [quant-ph]

  23. [32]

    Pawlowski, J

    J. Pawlowski, J. Tuziemski, P. Tarasiuk, A. Przy- bysz, R. Adamski, K. Hendzel, L. Pawela, and B. Gar- das, VeloxQ: A fast and efficient QUBO solver (2025), arXiv:2501.19221 [quant-ph]. 6

  24. [33]

    Zhang and J

    T. Zhang and J. Han, Quantized simulated bifurcation for the Ising model, in2023 IEEE 23rd International Conference on Nanotechnology (NANO)(2023) pp. 715– 720

  25. [34]

    D-Wave, D-Wave hybrid framework (2025), accessed: 2025-01-30. S1 Supplemental Material: Closing the Quantum-Classical Gap in approximate QUBO Optimization In the Supplemental Material we present results for multi-GPU implementation of the Simulated Bifurcation Ma- chine (SBM) ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.