Recent quantum runtime (dis)advantages

Basic Information

• Paper ID: 2510.06337
• Title: Recent quantum runtime (dis)advantages
• Authors: J. Tuziemski, J. Pawłowski, P. Tarasiuk, Ł. Pawela, B. Gardas
• Classification: quant-ph
• Publication Date: October 16, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2510.06337

Abstract

This paper re-evaluates recent claims of quantum advantage, particularly in quantum annealing and gate-based algorithms, testing whether reported speedups remain valid under rigorous end-to-end runtime definitions and comparison with strong classical benchmarks. Traditional analyses often overlook substantial overhead costs (readout, compilation, thermalization, etc.), leading to biased assessments. The authors review three important milestones: (1) quantum annealing for approximate QUBO; (2) restricted Simon problem; (3) BF-DCQO hybrid algorithm. Results indicate that runtime-based quantum advantage on NISQ hardware remains elusive.

Research Background and Motivation

Research Questions

The core question addressed by this paper is: Do current claims of quantum advantage remain valid under rigorous runtime definitions and fair classical benchmark comparisons?

Problem Significance

1. Practical Considerations: The ultimate goal of quantum computing is to surpass classical computation in practical applications, with runtime performance being a key indicator of practical value
2. Assessment Bias Issues: Existing research often overlooks significant quantum hardware overhead, leading to overly optimistic assessments of quantum advantage
3. Scientific Rigor: There is a need to establish fair and rigorous benchmarking methodologies to evaluate the true performance of quantum algorithms

Limitations of Existing Approaches

1. Improper Runtime Definition: Many studies consider only "pure computation" time, ignoring readout, thermalization, compilation, and other overhead
2. Benchmark Selection Bias: Classical benchmark algorithms are not properly chosen, failing to employ state-of-the-art parallelization methods
3. Insufficient Statistical Analysis: Lack of adequate statistical analysis with cherry-picking problems

Research Motivation

The authors argue that as quantum technology matures, more rigorous evaluation standards are needed to verify the authenticity of quantum advantage claims and avoid exaggerated claims that could mislead scientific judgment.

Core Contributions

1. Establishment of Rigorous Runtime Definition Framework: Proposes a comprehensive runtime definition encompassing all necessary components (programming, execution, readout, thermalization)
2. Re-evaluation of Three Important Quantum Advantage Claims:
   • Quantum annealing advantage on approximate QUBO problems
   • Query complexity advantage of the restricted Simon problem
   • Runtime advantage of the BF-DCQO hybrid algorithm
3. Revelation of Root Causes of Assessment Bias: Analyzes why quantum hardware struggles to achieve clear separation between "pure computation" and "overhead"
4. Provision of Fair Benchmarking Guidelines: Establishes evaluation standards and methodologies for future quantum advantage claims

Methodology Details

Task Definition

This paper re-evaluates quantum algorithm performance on the following three specific tasks:

• Input: Optimization problem instances, Oracle queries, HUBO problems
• Output: Problem solutions or query results
• Constraints: Actual runtime performance under current NISQ hardware limitations

Runtime Definition Framework

Quantum Annealing Device Runtime

The complete runtime for quantum annealing should include:

Total Runtime = Programming Time + Annealing Time + Readout Time + Thermalization Time

Key Findings:

• Readout time ~200μs, while annealing time is only 0.5-27μs
• Readout time is two orders of magnitude longer than annealing time
• This causes severe distortion in performance assessments based solely on annealing time

Digital Quantum Device Runtime

Complete runtime for digital quantum computing includes:

Total Runtime = Preprocessing Time + Compilation Time + Execution Time + Readout Time + Thermalization Time

Time-to-ε (TTε) Metric

$TTε = t_f \cdot \frac{\log(1-0.99)}{\log(1-p_{E≤E_0+ε|E_0})}$

Where:

• $t_f$: Time to generate a solution
• $p_{E≤E_0+ε|E_0}$: Probability of finding a solution within ε optimality gap

Technical Innovations

1. Comprehensive Runtime Accounting: First systematic inclusion of time overhead from all quantum computation phases
2. Strong Classical Benchmarks: Uses GPU-optimized parallel algorithms (e.g., SBM) as benchmarks
3. Statistical Rigor: Avoids cherry-picking through sufficient instance quantities and statistical analysis

Experimental Setup

Evaluation Cases

Case 1: Quantum Annealing for Approximate QUBO

• Dataset: Sidon-28 instances, scale N∈142, 1322
• Quantum Device: D-Wave quantum annealer
• Classical Benchmark: Simulated Bifurcation Machine (SBM)
• Metrics: TTε median

Case 2: Restricted Simon Problem

• Problem Scale: 29-bit input, Hamming weight w∈2,7
• Quantum Device: IBM Brisbane
• Classical Implementation: Brute-force algorithm on GPU
• Metrics: Oracle call count and actual runtime

Case 3: BF-DCQO Hybrid Algorithm

• Problem Type: Higher-order Unconstrained Binary Optimization (HUBO)
• Instance Scale: N∈80, 100, 130, 156
• Comparison Methods: CPLEX, Simulated Annealing, SBM

Implementation Details

• Hardware Environment: Dual Intel Xeon Platinum 8462Y+ CPUs, 4×NVIDIA H100 GPUs, 1TB RAM
• Statistical Methods: 50 random instances with multiple independent runs
• Parameter Optimization: All algorithms undergo hyperparameter tuning

Experimental Results

Main Results

Quantum Annealing Results

Using complete runtime definition:

• TTεMed Nearly Constant: Uncertainty in fitted exponent α is too large to draw non-zero conclusions
• Readout Time Dominates: Constitutes the main portion of total runtime
• SBM Outperforms: Demonstrates better scalability on identical problems

Restricted Simon Problem Results

• Query Complexity Advantage Exists: Quantum algorithm theoretically requires fewer Oracle calls
• Actual Runtime Disadvantage Significant:
  • N=29, w=7: Classical algorithm ~0.035s, quantum algorithm ~2s
  • Quantum algorithm ~100× slower
  • Predicted crossover point at N≈60, but noise limits practical achievability

BF-DCQO Hybrid Algorithm Results

• Methodological Issues: Inaccurate runtime estimation, overlooking important overhead
• Statistical Problems: Cherry-picking based on limited instances (5)
• Clear SBM Advantage: Superior performance on identical problems

Ablation Studies

Runtime Definition Sensitivity Analysis

Comparison of impact from different runtime definitions:

Results show quantum algorithms are extremely sensitive to runtime definition, while classical algorithms are relatively robust.

Case Analysis

Challenges of HUBO Instances

Generated HUBO instances exhibit different difficulty levels for different algorithms:

• SBM: Lower success rate on Cauchy distribution instances, but clear runtime advantage
• SA(QUBO): Best solution quality, but longer runtime
• SA(HUBO): Superior performance on Pareto distribution instances

This demonstrates that instance characteristics significantly impact algorithm performance, necessitating adequate statistical analysis.

Related Work

Theoretical Foundations of Quantum Advantage

• Simon's Algorithm: Exponential query complexity separation
• Shor's Algorithm: Based on factorization hardness assumption
• Random Circuit Sampling: First experimental quantum advantage claim

Heuristic Quantum Algorithms

• Quantum Annealing: Seeking advantage on specific NP-hard problem instances
• Variational Quantum Algorithms: Primary direction in the NISQ era
• Hybrid Quantum-Classical Algorithms: Combining advantages of both computing paradigms

Benchmarking Methodologies

• TTε Metric: Standard evaluation method for approximate optimization
• Query Complexity Framework: Important tool for theoretical analysis
• Classical Benchmark Selection: Critical factor affecting validity of quantum advantage claims

Conclusions and Discussion

Main Conclusions

1. Runtime Quantum Advantage on NISQ Hardware Remains Elusive: Under rigorous runtime definitions and fair benchmark comparisons, all examined quantum advantage claims do not hold
2. Runtime Definition is Paramount: High overhead in quantum hardware makes separation between "pure computation" and "overhead" difficult; complete runtime must be used
3. Importance of Classical Benchmark Selection: Using state-of-the-art parallelized classical algorithms as benchmarks is prerequisite for fair evaluation
4. Statistical Rigor is Essential: Sufficient instance quantities and statistical analysis are indispensable for credible quantum advantage claims

Limitations

1. Hardware Constraints: Evaluation limited to current NISQ devices; future fault-tolerant quantum computers may alter conclusions
2. Problem Scale: Limited by current quantum hardware scale, unable to assess asymptotic behavior on large-scale problems
3. Algorithm Coverage: Only specific quantum algorithms evaluated; cannot represent all possible quantum approaches

Future Directions

1. Improved Runtime Measurement Methods: Develop more precise quantum algorithm runtime measurement tools
2. Stronger Classical Benchmarks: Continuously track latest advances in classical algorithms
3. Fault-Tolerant Quantum Computing Evaluation: Establish evaluation frameworks for future fault-tolerant quantum devices
4. Novel Evaluation Metrics: Beyond runtime, consider other practical indicators such as energy consumption and cost

In-Depth Evaluation

Strengths

1. Rigorous Methodology: Establishes a comprehensive and fair quantum algorithm evaluation framework
2. Comprehensive Experiments: Covers three important quantum advantage claims with well-designed experiments
3. Statistical Reliability: Uses adequate sample sizes, avoiding cherry-picking bias
4. High Practical Value: Provides important methodological guidance for the quantum computing community
5. Clear Writing: Logical structure and accurate technical detail descriptions

Weaknesses

1. Limited Coverage: Evaluates only three specific cases, potentially insufficient comprehensiveness
2. Hardware Dependency: Conclusions may change with advances in quantum hardware technology
3. Classical Algorithm Bias: Possible optimization bias toward classical methods
4. Insufficient Theoretical Analysis: Focuses more on experimental results with relatively limited theoretical analysis

Impact

1. Academic Impact: Establishes new standards for quantum advantage evaluation, potentially influencing future research directions
2. Practical Value: Helps researchers and investors more objectively assess the current state of quantum computing
3. Policy Significance: Provides scientific evidence for quantum computing investment and policy decisions
4. Strong Reproducibility: Provides complete code and data for verification and extension

Applicable Scenarios

1. Quantum Algorithm Evaluation: Provides methodology for performance assessment of new quantum algorithms
2. Investment Decisions: Offers objective technical assessment for quantum computing investments
3. Research Direction Guidance: Helps researchers identify truly promising quantum applications
4. Education and Training: Serves as important reference material for quantum computing courses

References

This paper cites important literature in the quantum computing field, including:

1. Feynman, R.P. - Pioneering work on quantum computation
2. Shor, P. - Quantum factorization algorithm
3. Simon, D.R. - Original Simon algorithm paper
4. Arute, F. et al. - Google's quantum advantage claim
5. Munoz-Bauza, H. & Lidar, D. - Quantum annealing advantage claims

Overall Assessment: This is a paper of significant academic and practical value that, through rigorous experimentation and analysis, provides important insights to the quantum computing community regarding quantum advantage evaluation. While its conclusions may disappoint some quantum computing advocates, its scientific rigor and methodological contributions have positive significance for field development.