Recent quantum runtime (dis)advantages

This paper argues that current claims of quantum advantage are often biased by excluding substantial system-level overheads, and through experimentally grounded end-to-end runtime definitions and strong classical baselines, demonstrates that no credible runtime advantage has yet been achieved on NISQ hardware for the examined annealing and gate-based algorithms.

The Gist

Imagine you are a race car judge trying to decide if a new, futuristic electric car (the Quantum Computer) is actually faster than a high-performance sports car (the Classical Computer).

The authors of this paper, a team of researchers from Poland, decided to take a fresh look at recent claims that the electric car is winning. They found that while the electric car looks fast on the dashboard, a closer look at the whole race reveals it's actually losing.

Here is the breakdown of their findings using simple analogies:

The Core Problem: "The Stopwatch vs. The Lap Time"

In the past, when people compared these computers, they often only timed the moment the engine was actually revving (the "computation"). They ignored the time it took to:

• Start the engine.
• Put the car in gear.
• Check the tires.
• Read the speedometer at the finish line.

The authors argue that for quantum computers, these "extra steps" take so much time that they completely ruin the speed advantage. You can't just time the engine; you have to time the entire trip from the garage to the finish line.

Case Study 1: The Quantum Annealer (The "Slow Readout" Race)

The Claim: A recent study said a quantum annealer (a type of quantum computer that solves optimization problems) was getting faster as problems got bigger.
The Reality Check: The authors re-ran the experiment but timed the whole process, including reading the results.

• The Analogy: Imagine a runner who sprints the 100 meters in 0.5 seconds (the quantum part). But, every time they finish, they have to walk slowly back to the starting line to get their time recorded, which takes 200 seconds.
• The Result: The "sprint" is fast, but the "walking back" is so slow that the total time doesn't get any better as the race gets longer. The quantum computer is currently dominated by the time it takes to "read the answer," making it no faster than the best classical computers for these tasks.

Case Study 2: Simon's Problem (The "Magic Trick" vs. The "Calculator")

The Claim: Another study showed a quantum computer solving a specific math puzzle (Simon's problem) using far fewer "questions" (oracle calls) than a classical computer. It looked like a magic trick where the quantum computer needed only a few guesses while the classical one needed millions.
The Reality Check: The authors looked at the actual time it took to solve the puzzle on a real machine.

• The Analogy: The quantum computer is like a wizard who can guess the answer in 1 second, but the wizard is very slow at casting the spell and reading the result. The classical computer is a super-fast calculator that needs to ask a million questions, but it asks them so quickly that it finishes the whole job in 0.03 seconds.
• The Result: Even though the quantum computer asked fewer questions, the "overhead" of running the spell made it 100 times slower in real-world time. The "magic" isn't fast enough yet to beat the calculator.

Case Study 3: The Hybrid Algorithm (The "Unfair Race")

The Claim: A third study claimed a hybrid quantum-classical algorithm was the fastest way to solve complex business problems.
The Reality Check: The authors found two major issues:

1. The Stopwatch was broken: They didn't count the time spent tuning the settings (hyperparameters) or the time the classical computer spent helping the quantum one.
2. The Opponent was weak: They compared the quantum computer against a "slow" classical algorithm (CPLEX) that wasn't optimized for the specific type of problem.

• The Analogy: It was like comparing a Ferrari to a bicycle, but only timing the Ferrari's engine and ignoring the time it took to drive to the track. When the authors put a proper, high-speed sports car (a tuned classical algorithm) in the race, the quantum "Ferrari" didn't win. In fact, the classical car was faster.

The Big Conclusion

The paper concludes that we haven't actually seen a "quantum advantage" in real-world speed yet.

Just because a quantum computer has a theoretical advantage (like needing fewer steps) doesn't mean it wins the race today. The "overhead" (setup, reading results, cooling, etc.) is currently too heavy.

The Authors' Advice for Future Races:
To prove quantum computers are truly faster, future studies must:

1. Time the whole trip: Include setup, reading, and cooling in the stopwatch.
2. Pick a fair opponent: Compare against the best, most modern classical computers, not outdated ones.
3. Be honest about the stats: Don't just pick the one race where the quantum car won; look at the average performance.

Until these conditions are met, the "quantum advantage" remains a promise for the future, not a reality for today.

Technical Summary

1. Problem Statement

The central problem addressed is the lack of a robust, experimentally grounded definition of quantum runtime used to claim "quantum advantage." Current claims often rely on:

• Proxy metrics: Using "annealing time" or "oracle call complexity" as a substitute for total wall-clock time.
• Excluded overheads: Ignoring system-level costs such as readout, thermalization, transpilation (compilation), data transfer, and hyperparameter tuning.
• Weak baselines: Comparing quantum algorithms against suboptimal classical implementations (e.g., sequential algorithms or those requiring problem reformulation).

The authors argue that without accounting for the end-to-end runtime (from problem submission to solution extraction), claims of quantum advantage on current Noisy Intermediate-Scale Quantum (NISQ) hardware are often biased and misleading.

2. Methodology

The authors propose a framework for operationally meaningful runtime definitions and apply it to three representative case studies involving recent high-profile claims of quantum advantage.

A. Proposed Runtime Definitions

• Quantum Annealing: Total runtime ($t_{tot}$) must include:
  • Programming time (loading the problem).
  • Annealing time ($t_{anneal}$).
  • Readout time (measuring the state).
  • Thermalization time (resetting the device).
  • Cloud access overheads.
• Gate-Based (Digital) Quantum: Total runtime must include:
  • Transpilation (compiling the circuit to native gates/topology).
  • Execution time (shots).
  • Readout and thermalization between shots.
  • Classical post-processing and data transfer.
• Classical Baselines: Reference algorithms must be:
  • Parallelizable: Utilizing modern hardware (GPUs/FPGAs).
  • Native: Solving the problem without unnecessary reformulation (e.g., avoiding converting Higher-Order Unconstrained Binary Optimization (HUBO) to Mixed-Integer Programming if a native solver exists).
  • Optimized: Including hyperparameter tuning costs.

B. Case Studies Analyzed

1. Quantum Annealing for Approximate QUBO: Re-evaluating Ref. [20] (Munoz-Bauza & Lidar).
2. Gate-Based Oracle Query (Simon's Problem): Re-evaluating Ref. [21] (Singkanipa et al.).
3. Hybrid BF-DCQO Algorithm: Re-evaluating Ref. [22] (Chandarana et al.) for HUBO problems.

3. Key Contributions & Results

Case Study 1: Quantum Annealing (Approximate QUBO)

• Original Claim: Ref. [20] reported a scaling advantage for quantum annealing over a classical reference (PT-ICM) based on "annealing time" ($t_{anneal}$).
• Re-evaluation: The authors measured the total QPU access time (including readout and thermalization).
• Finding:
  • Readout time (~200 µs) dominates the total runtime, exceeding the annealing time (0.5–27 µs) by 1–2 orders of magnitude.
  • When using the full end-to-end metric ($TT_\epsilon$), the scaling advantage disappears; the runtime remains nearly constant across problem sizes.
  • Comparison: A classical Simulated Bifurcation Machine (SBM) running on a GPU outperforms the quantum annealer even under optimistic assumptions, showing robust scaling where the quantum device shows none.

Case Study 2: Gate-Based Oracle Query (Restricted Simon's Problem)

• Original Claim: Ref. [21] demonstrated an exponential advantage in query complexity (number of oracle calls) for a restricted Simon's problem on IBM hardware.
• Re-evaluation: The authors compared the wall-clock runtime of the quantum implementation against a classical brute-force algorithm running on a single GPU.
• Finding:
  • While the quantum algorithm requires exponentially fewer oracle calls, the physical time per call is significantly slower due to gate execution and readout overheads.
  • Result: For the tested size ($N=29$ bits), the classical GPU implementation solved the problem in ~0.035s, while the quantum implementation took ~2s (a ~100x slowdown).
  • Crossover Point: Theoretical extrapolation suggests a runtime crossover only at $N \approx 60$, a size currently impossible for noisy devices to solve correctly.

Case Study 3: Hybrid BF-DCQO Algorithm (HUBO)

• Original Claim: Ref. [22] claimed a runtime advantage for a digitized counter-diabatic quantum algorithm (BF-DCQO) over Simulated Annealing (SA) and CPLEX for HUBO problems.
• Re-evaluation:
  • Baseline Flaws: The original study used a suboptimal classical baseline (CPLEX required reformulating HUBO to Mixed-Integer Programming, adding massive overhead) and reported results for single "best" instances rather than statistical averages.
  • New Baseline: The authors implemented a GPU-accelerated, native HUBO Simulated Annealing solver and compared it against BF-DCQO.
  • Result: The optimized classical SA outperformed the hybrid quantum approach in both solution quality and time-to-ratio ($TTR$).
  • Embedding Issue: When testing the same instances on a D-Wave Advantage2 annealer, the required embedding (mapping to hardware topology) resulted in long chains and poor solution quality, further negating any potential advantage.

4. Significance and Conclusions

Main Conclusion

Under experimentally grounded, end-to-end performance metrics, no practical runtime quantum advantage has been demonstrated on current NISQ hardware. The observed "advantages" in recent literature are artifacts of:

1. Ignoring dominant overheads (readout, compilation, thermalization).
2. Using weak or non-native classical baselines.
3. Relying on asymptotic complexity metrics (like query complexity) that do not translate to wall-clock speed for small problem sizes.

Proposed Principles for Future Benchmarking

The authors outline a set of principles to ensure credible claims of quantum advantage:

1. Primary Runtime Measurement: Measure total execution time directly, not inferred from nominal parameters.
2. Comprehensive Overhead Accounting: Include all system-level costs (readout, data transfer, tuning).
3. Standardized Metrics: Use metrics like Time-to-$\epsilon$ ($TT_\epsilon$) across diverse instances.
4. Scaling Integrity: Analyze scaling over a broad range of problem sizes to avoid finite-size effects.
5. High-Performance Classical Baselines: Compare against state-of-the-art, parallelized classical solvers (e.g., GPU-based SBM or SA).
6. The Hybrid Null Hypothesis: For hybrid algorithms, test if replacing the quantum subroutine with a classical one yields similar or better performance.

Impact

This work serves as a critical reality check for the quantum computing field. It emphasizes that while theoretical speedups exist, the engineering reality of current hardware (noise, latency, overhead) currently prevents these from translating into practical utility. Credible claims of advantage require rigorous, reproducible, and holistic benchmarking that treats quantum and classical systems with equal operational scrutiny.