Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.06337 · Physical Review Applied

Limits of quantum run-time advantage

Jan Tuziemski, Jakub Pawłowski, Paweł Tarasiuk, Łukasz Pawela, Bartłomiej Gardas

Published Mar 17, 2026• 1 citation
arXivHTMLPDF

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-$ε$ 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.

DOI
10.1103/gpsf-pn1x

Related papers

Assessing Claims of Advantage in Quantum Machine Learning: A Critical Review

Stefan Klug, Maximilian Moll

Abstract Quantum machine learning (QML) has attracted growing interest because quantum states and circuits may provide new representational primitives for learning, yet progress remains constrained by noisy intermediate-scale quantum (NISQ) hardware and heterogeneous evaluation practices. This article presents a critical review of recent QML architectures and representative empirical and theoretical studies, with emphasis on work published since 2022 alongside selected seminal references. To improve comparability, “quantum advantage” is assessed in three distinct senses: computational scaling under stated input-access assumptions, empirical predictive performance in the benchmark setting considered, and resource efficiency at a fixed budget accounting for both classical compute and quantum execution, including shot costs. Organized by architecture family and application domain, the review analyzes how baseline strength, hyperparameter optimization, preprocessing, and budget reporting shape conclusions. Overall, quantum feature maps and kernels, as well as variational (often hybrid) pipelines, can be competitive on selected small- to medium-scale benchmarks, but robust end-to-end evidence for a general practical advantage remains limited. Reported gains are often sensitive to budget matching and may be dominated by measurement overheads, dataset and preprocessing effects, and training instabilities. The review concludes that credible progress requires standardized benchmarking, transparent end-to-end resource accounting, and hardware-centered evaluations that test scalability and robustness beyond toy regimes.

•May 7, 2026•0 citations

Realistic Runtime Analysis for Quantum Simplex Computation

Sabrina C. L. Ammann, Maximilian Hess, Debora Ramacciotti +10 more

In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic worst-case bounds. Can we expect this to have consequences for Linear and Integer Programming when solving instances of practically relevant size, a fundamental goal of Mathematical Programming, Operations Research and Algorithm Engineering? Answering this question faces a crucial impediment: The lack of sufficiently large quantum platforms prevents performing real-world tests for comparison with classical methods. In this paper, we present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. To this end, we measure the expected practical performance of quantum computers by analyzing the expected gate complexity of a quantum algorithm. The lack of practical quantum platforms for experimental comparison is addressed by hybrid benchmarking, in which the algorithm is performed on a classical system, logging the expected cost of the various subroutines that are employed by the quantum versions. In particular, we provide an analysis of quantum methods for Linear Programming, for which recent work has provided asymptotic speedup through quantum subroutines for the Simplex method. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.

arXiv:2311.09995•Nov 16, 2023•2 citations

Assessing The Reality of Quantum Advantage in Machine Learning

Shridhar Jalindar Shelke, Purvaja Mahajan, Atharav Arvind Pujari +1 more

Quantum computing has generated significant expectations for its potential to enhance machine learning (ML) tasks, with theoretical research proposing computational advantages ranging from polynomial to exponential speedups for specific subroutines.However, a critical disconnect remains: theoretical or asymptotic speedup claims do not automatically imply a practical, end-to-end advantage.Current evidence does not clearly establish whether these claimed advantages translate into measurable superiority over optimised classical approaches.This review critically assesses the relationship between theoretical claims of quantum advantage and the currently available practical and experimental evidence.We critically examine the evidence and assumptions underlying claimed speedups, including the overheads associated with data encoding and access, as well as the use of appropriate and competitive classical baselines for fair comparison.The scope of this assessment covers key limiting factors, such as scalability, trainability, hardware noise in the noisy intermediate-scale quantum (NISQ) era, and overall resource requirements.By distinguishing between theoretical potential and demonstrated practical performance, this work identifies where current evidence is convincing and where it remains insufficient.The review identifies the specific conditions required for the credible validation of quantum advantage and argues that future progress must be positioned around rigorous, realistic, and end-to-end evaluation rather than theoretical complexity claims alone.

International Journal of Innovative Research in Technology•Oct 13, 2026•0 citations

Quantum Advantage in the NISQ Era - Algorithms, Benchmarks, and Practical Limitations

Akella, Pathanjali Sastri,, Akelle Srinivasa Rao, V N R Sai Krishna Kari

The current stage of quantum computing development is defined by Noisy Intermediate-Scale Quantum (NISQ) devices, which operate with a moderate number of qubits that are inherently susceptible to noise and decoherence. Despite the absence of full error correction, NISQ systems have demonstrated the ability to perform computational tasks that challenge classical simulation under certain conditions. This paper explores the concept of quantum advantage in the NISQ era by analysing prominent algorithmic approaches, benchmarking methodologies, and the practical constraints imposed by contemporary hardware. Hybrid quantum–classical algorithms, sampling-based experiments, and performance metrics are examined to assess the extent to which near-term quantum devices can outperform classical systems. The study finds that while progress toward quantum advantage is evident, significant technical and algorithmic limitations prevent its widespread realization. The paper concludes by identifying key research directions required to bridge the gap between experimental demonstrations and practical quantum computing applications.

Journal of Analytical and Applied Computer Sciences•Dec 31, 2025•0 citations

A Review and Collection of Metrics and Benchmarks for Quantum Computers: definitions, methodologies and software

Deep Lall, Abhishek Agarwal, Weixi Zhang +15 more

Quantum computers have the potential to provide an advantage over classical computers in a number of areas. Numerous metrics to benchmark the performance of quantum computers, ranging from their individual hardware components to entire applications, have been proposed over the years. Objective comparisons are further hampered in practice as different variations of the same metric are used, and the data disclosed together with a reported metric value is often not sufficient to reproduce the measurements. In this poster, we present our recent article, where we address these challenges by providing a review of metrics and benchmarks for quantum computers [1], including 1) a comprehensive collection of benchmarks allowing holistic comparisons of quantum computers, 2) a consistent format of the definitions across all metrics including a transparent description of the methodology and of the main assumptions and limitations, and 3) a reproducible approach by linking the metrics to open-source software used to evaluate them . We identify five areas where international standardization working groups could be established, namely: i) the identification and agreement on the categories of metrics that comprehensively benchmark device performance; ii) the identification and agreement on a set of well-established metrics that together comprehensively benchmark performance; iii) the identification of metrics specific to hardware platforms, including non-gate-based quantum computers; iv) inter-laboratory comparison studies to develop best practice guides for measurement methodology; and v) agreement on what data and software should be reported together with a metric value to ensure trust, transparency and reproducibility. We provide potential routes to advancing these areas. We expect that this work will accelerate the progress of quantum computing hardware towards quantum advantage. [1] D. Lall et al., A Review and Collection of Metrics and Benchmarks for Quantum Computers: Definitions, Methodologies and Software, arXiv:2502.06717.

arXiv:2502.06717•Jan 1, 2025•3 citations

ADVANCEMENTS IN QUANTUM COMPUTING: EXPLORING THE POTENTIAL OF QUANTUM ALGORITHMS FOR SOLVING COMPLEX PROBLEMS IN PHYSICS

Hamza Farid, Amina Siddiq

Quantum computing has emerged as a promising paradigm for addressing computational challenges in physics that remain intractable for classical methods. This study presents a quantitative benchmarking analysis of prominent quantum algorithms applied to representative physics problem classes, with the objective of evaluating their computational performance relative to state-of-the-art classical algorithms. Using standardized performance metrics—including execution time, algorithmic complexity, resource utilization, accuracy, scalability, and quantum advantage ratios—the study systematically compares quantum and classical approaches across multiple experimental configurations. The results demonstrate that quantum algorithms exhibit measurable performance gains for specific problem types, particularly in terms of runtime efficiency and scaling behavior, while also highlighting practical constraints related to qubit requirements and circuit depth. Visual and tabulated analyses further reveal that quantum advantage is highly problem-dependent and influenced by algorithmic structure and system size. Overall, the findings provide empirical evidence that quantum algorithms can offer substantial computational benefits for selected physics applications, while underscoring the importance of quantitative benchmarking in distinguishing theoretical promise from practical performance. This work contributes to ongoing efforts to objectively assess quantum advantage and informs future research directions in quantum algorithm development and physics-based applications.

Innovations in Science, Technology, and Society•Dec 31, 2025•0 citations
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-εεε 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.
Abstract Quantum machine learning (QML) has attracted growing interest because quantum states and circuits may provide new representational primitives for learning, yet progress remains constrained by noisy intermediate-scale quantum (NISQ) hardware and heterogeneous evaluation practices. This article presents a critical review of recent QML architectures and representative empirical and theoretical studies, with emphasis on work published since 2022 alongside selected seminal references. To improve comparability, “quantum advantage” is assessed in three distinct senses: computational scaling under stated input-access assumptions, empirical predictive performance in the benchmark setting considered, and resource efficiency at a fixed budget accounting for both classical compute and quantum execution, including shot costs. Organized by architecture family and application domain, the review analyzes how baseline strength, hyperparameter optimization, preprocessing, and budget reporting shape conclusions. Overall, quantum feature maps and kernels, as well as variational (often hybrid) pipelines, can be competitive on selected small- to medium-scale benchmarks, but robust end-to-end evidence for a general practical advantage remains limited. Reported gains are often sensitive to budget matching and may be dominated by measurement overheads, dataset and preprocessing effects, and training instabilities. The review concludes that credible progress requires standardized benchmarking, transparent end-to-end resource accounting, and hardware-centered evaluations that test scalability and robustness beyond toy regimes.
In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic worst-case bounds. Can we expect this to have consequences for Linear and Integer Programming when solving instances of practically relevant size, a fundamental goal of Mathematical Programming, Operations Research and Algorithm Engineering? Answering this question faces a crucial impediment: The lack of sufficiently large quantum platforms prevents performing real-world tests for comparison with classical methods. In this paper, we present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. To this end, we measure the expected practical performance of quantum computers by analyzing the expected gate complexity of a quantum algorithm. The lack of practical quantum platforms for experimental comparison is addressed by hybrid benchmarking, in which the algorithm is performed on a classical system, logging the expected cost of the various subroutines that are employed by the quantum versions. In particular, we provide an analysis of quantum methods for Linear Programming, for which recent work has provided asymptotic speedup through quantum subroutines for the Simplex method. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
Quantum computing has generated significant expectations for its potential to enhance machine learning (ML) tasks, with theoretical research proposing computational advantages ranging from polynomial to exponential speedups for specific subroutines.However, a critical disconnect remains: theoretical or asymptotic speedup claims do not automatically imply a practical, end-to-end advantage.Current evidence does not clearly establish whether these claimed advantages translate into measurable superiority over optimised classical approaches.This review critically assesses the relationship between theoretical claims of quantum advantage and the currently available practical and experimental evidence.We critically examine the evidence and assumptions underlying claimed speedups, including the overheads associated with data encoding and access, as well as the use of appropriate and competitive classical baselines for fair comparison.The scope of this assessment covers key limiting factors, such as scalability, trainability, hardware noise in the noisy intermediate-scale quantum (NISQ) era, and overall resource requirements.By distinguishing between theoretical potential and demonstrated practical performance, this work identifies where current evidence is convincing and where it remains insufficient.The review identifies the specific conditions required for the credible validation of quantum advantage and argues that future progress must be positioned around rigorous, realistic, and end-to-end evaluation rather than theoretical complexity claims alone.
The current stage of quantum computing development is defined by Noisy Intermediate-Scale Quantum (NISQ) devices, which operate with a moderate number of qubits that are inherently susceptible to noise and decoherence. Despite the absence of full error correction, NISQ systems have demonstrated the ability to perform computational tasks that challenge classical simulation under certain conditions. This paper explores the concept of quantum advantage in the NISQ era by analysing prominent algorithmic approaches, benchmarking methodologies, and the practical constraints imposed by contemporary hardware. Hybrid quantum–classical algorithms, sampling-based experiments, and performance metrics are examined to assess the extent to which near-term quantum devices can outperform classical systems. The study finds that while progress toward quantum advantage is evident, significant technical and algorithmic limitations prevent its widespread realization. The paper concludes by identifying key research directions required to bridge the gap between experimental demonstrations and practical quantum computing applications.
Quantum computers have the potential to provide an advantage over classical computers in a number of areas. Numerous metrics to benchmark the performance of quantum computers, ranging from their individual hardware components to entire applications, have been proposed over the years. Objective comparisons are further hampered in practice as different variations of the same metric are used, and the data disclosed together with a reported metric value is often not sufficient to reproduce the measurements. In this poster, we present our recent article, where we address these challenges by providing a review of metrics and benchmarks for quantum computers [1], including 1) a comprehensive collection of benchmarks allowing holistic comparisons of quantum computers, 2) a consistent format of the definitions across all metrics including a transparent description of the methodology and of the main assumptions and limitations, and 3) a reproducible approach by linking the metrics to open-source software used to evaluate them . We identify five areas where international standardization working groups could be established, namely: i) the identification and agreement on the categories of metrics that comprehensively benchmark device performance; ii) the identification and agreement on a set of well-established metrics that together comprehensively benchmark performance; iii) the identification of metrics specific to hardware platforms, including non-gate-based quantum computers; iv) inter-laboratory comparison studies to develop best practice guides for measurement methodology; and v) agreement on what data and software should be reported together with a metric value to ensure trust, transparency and reproducibility. We provide potential routes to advancing these areas. We expect that this work will accelerate the progress of quantum computing hardware towards quantum advantage. [1] D. Lall et al., A Review and Collection of Metrics and Benchmarks for Quantum Computers: Definitions, Methodologies and Software, arXiv:2502.06717.
Quantum computing has emerged as a promising paradigm for addressing computational challenges in physics that remain intractable for classical methods. This study presents a quantitative benchmarking analysis of prominent quantum algorithms applied to representative physics problem classes, with the objective of evaluating their computational performance relative to state-of-the-art classical algorithms. Using standardized performance metrics—including execution time, algorithmic complexity, resource utilization, accuracy, scalability, and quantum advantage ratios—the study systematically compares quantum and classical approaches across multiple experimental configurations. The results demonstrate that quantum algorithms exhibit measurable performance gains for specific problem types, particularly in terms of runtime efficiency and scaling behavior, while also highlighting practical constraints related to qubit requirements and circuit depth. Visual and tabulated analyses further reveal that quantum advantage is highly problem-dependent and influenced by algorithmic structure and system size. Overall, the findings provide empirical evidence that quantum algorithms can offer substantial computational benefits for selected physics applications, while underscoring the importance of quantitative benchmarking in distinguishing theoretical promise from practical performance. This work contributes to ongoing efforts to objectively assess quantum advantage and informs future research directions in quantum algorithm development and physics-based applications.