Runtime Quantum Advantage with Digital Quantum Optimization [arXiv:2505.08663]

In this talk, I will present our recent work on the bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm, providing experimental evidence of runtime quantum advantage on commercially available superconducting quantum computers with 156 qubits. We benchmark BF-DCQO on a range of higher-order unconstrained binary optimization problems that are difficult for classical methods, comparing time-to-solution and time-to-approximate-solution metrics against various classical algorithms, including heuristics such as simulated annealing and memetic tabu search, as well as exact solvers such as CPLEX and Gurobi on multicore CPUs. Classical solvers typically require fractions of a minute, whereas the quantum runs return comparable or better solutions within a few seconds, demonstrating a runtime quantum advantage. Our analysis shows that this performance improvement becomes more pronounced as the system size increases. The talk will cover instance design, evaluation methodology, and scaling behavior, and will conclude with a perspective on how ongoing hardware and algorithmic advances could extend these gains, potentially by orders of magnitude, and enable quantum usefulness for practical industrial applications even before fully fault-tolerant quantum computers are available.