Toward quantum scaling advantage in approximate optimization

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.