Recent quantum runtime (dis)advantages

Abstract

A robust definition of quantum runtime is essential for assessing the performance of quantum algorithms and claims of quantum advantage. While for most classical hardware the total runtime is well approximated by computation plus a weakly varying constant, on current quantum hardware a clean experimental separation between "pure computation" and "overhead" is often not justified. Consequently, conventional quantum runtime analyses excluding substantial system-level overheads can lead to biased performance assessments. In this work we introduce experimentally grounded, end-to-end definitions of quantum runtime for digital and analogue quantum computers, together with a methodology for selecting strong classical baselines for quantum-classical runtime comparisons. Within this framework, we evaluate recent claims of quantum advantage in annealing and gate-based algorithms. We examine three representative case studies. First, we revisit annealing for approximate QUBO problems PRL 134, 160601 (2025), which employs a well-motivated time-to-$\epsilon$ metric but effectively uses annealing time as a proxy for runtime. Second, we analyze a restricted implementation of Simon's problem PRX 15, 021082 (2025), where the favorable scaling in oracle calls is undisputed; however, we show that the estimated runtime of the quantum experiment is approximately two orders of magnitude slower than a tuned classical baseline at the tested sizes. Finally, we find that the runtime advantage of the BF-DCQO hybrid algorithm arXiv:2505.08663 is not observed under more comprehensive benchmarking. Therefore, on current NISQ hardware, runtime-based quantum advantage has not yet been demonstrated under experimentally grounded performance metrics, and credible claims require careful time accounting, appropriate performance measures, and properly chosen classical reference implementations, as discussed in this work.

22 pages

References in corpus (26)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Parallel Tempering: Theory, Applications, and New Perspectives
• Validating quantum computers using randomized model circuits
• Defining and detecting quantum speedup
• Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
• Barren Plateaus in Variational Quantum Computing
• Challenges and Opportunities in Quantum Optimization
• Topological and subsystem codes on low-degree graphs with flag qubits
• Solving the sampling problem of the Sycamore quantum circuits
• Phase transition in Random Circuit Sampling
• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
• Simulated bifurcation for higher-order cost functions
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Energy-Consumption Advantage of Quantum Computation
• Opening the Black Box Inside Grover's Algorithm
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• Highly Versatile FPGA-Implemented Cyber Coherent Ising Machine
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Alleviating the quantum Big-$M$ problem
• Algorithm for the replica redistribution in the implementation of parallel annealing method on the hybrid supercomputer architecture
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization