Source-linked AI summary
Defining and detecting quantum speedup
Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, Matthias Troyer
TL;DR
The paper addresses how to define and detect quantum speedup fairly when comparisons are subtle. It proposes comparison and scaling principles, then applies them to a 503-qubit D-Wave Two benchmark against simulated annealers. The full benchmark shows no evidence of quantum speedup, while subset comparisons are inconclusive and limited by suboptimal annealing times.
Problem
The central problem is how to fairly compare classical and quantum devices and detect speedup when exponential separation is unavailable or the relevant classical baseline is uncertain.
Method
The paper defines limited quantum speedup and evaluates D-Wave Two using scaling, quantile, timing, and resource-matched comparisons with corresponding classical algorithms.
Results
The benchmark finds no evidence of limited quantum speedup for DW2 over simulated annealing across the full dataset, while instance-by-instance subset comparisons are inconclusive.
Takeaways & Limitations
Quantum speedup is elusive and its assessment depends on the comparison goal, selected instances, timing measure, and optimization of both devices.
Takeaways & Limitations
The instance-level possibility of speedup may be an artifact because DW2 uses suboptimal annealing times for most corresponding problem instances.
Abstract
from arXiv · showhide
The development of small-scale digital and analog quantum devices raises the question of how to fairly assess and compare the computational power of classical and quantum devices, and of how to detect quantum speedup. Here we show how to define and measure quantum speedup in various scenarios, and how to avoid pitfalls that might mask or fake quantum speedup. We illustrate our discussion with data from a randomized benchmark test on a D-Wave Two device with up to 503 qubits. Comparing the performance of the device on random spin glass instances with limited precision to simulated classical and quantum annealers, we find no evidence of quantum speedup when the entire data set is considered, and obtain inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results for one particular benchmark do not rule out the possibility of speedup for other classes of problems and illustrate that quantum speedup is elusive and can depend on the question posed.
I. INTRODUCTION
Quantum speedup is straightforward to characterize when quantum performance is exponentially better, but subtler when the comparison is polynomial or hardware-specific. The paper distinguishes several comparison targets and introduces limited quantum speedup for corresponding classical and quantum approaches.
- Motivation: Polynomial quantum speedup requires more careful definitions and detection than exponential speedup.The difficulty includes defining problem hardness when prior knowledge about the answer is available.
- Benchmark: The paper uses random spin-glass benchmarks to compare a 503-qubit D-Wave Two device with classical algorithms and simulated quantum annealing.Quantum annealing speedup for these problems remains an open question in the paper’s framing.
- Measurement goals: Speedup can be measured by quantile ratios for optimizer performance or by quantiles of instance-by-instance time ratios for selected subsets.The choice depends on whether the goal is solving almost all inputs or studying performance on some instances.
- Definitions: The relevant classical baseline varies because the best classical algorithm may be unknown or lack community-wide consensus.The paper therefore also discusses potential speedup relative to a specified classical algorithm or set of algorithms.
- Definitions: Limited quantum speedup compares a candidate quantum processor with corresponding classical algorithms implementing the same algorithmic approach.For quantum annealing, corresponding methods can include simulated annealing, classical spin dynamics, or simulated quantum annealing.
III. CLASSICAL AND QUANTUM ANNEALING OF A SPIN GLASS
The benchmark studies Ising spin-glass ground states on Chimera graphs using simulated annealing, simulated quantum annealing, and a D-Wave device. Success probabilities are estimated against exact ground-state energies, while Figure 1 illustrates scaling at fixed annealing times.
- Problem definition: The benchmark uses Ising spin glasses whose zero-field ground-state problem is computationally difficult on the studied graph family.The instances use spins on graph vertices, with local fields and couplings defining each problem instance.
- Methods: SA, SQA, and the DW2 are compared as heuristic methods for finding Ising-model ground states.The exact ground-state energy is obtained with belief propagation for evaluating annealing outcomes.
- Methods: At least 1000 annealing repetitions per instance estimate the probability of finding the exact ground state.The repetitions are checked against the exact result to estimate success probabilities.
- Scaling benchmark: Figure 1 reports median time to find a ground state with 99% probability for ±1-coupling, zero-field spin glasses under fixed annealing times.The red envelope gives the minimal time at each problem size and is the relevant curve for asymptotic scaling.
IV. CONSIDERATIONS WHEN COMPUTING QUANTUM SPEEDUP
Reliable speedup estimates require size-dependent optimization, asymptotically relevant timing measures, and matched hardware resources. Fixed or inefficient settings can create apparent speedup that disappears under proper scaling analysis.
- Asymptotic scaling: Figure 2 contrasts true slowdown under optimal SA and SQA settings with fake speedup caused by an excessively long fixed SQA annealing time.The apparent speedup is an upper bound because the fixed-time SQA effort is suboptimally low in the relevant comparison.
- Asymptotic scaling: Fixed annealing times cannot determine asymptotic scaling because small-size inefficiencies can flatten the observed curves.The optimal annealing time must be found separately for each problem size.
- Resource usage: Quantum and classical comparisons must scale hardware resources and parallelism comparably to avoid mistaking parallel speedup for quantum speedup.The classical counterpart is a hypothetical parallel simulated annealer with the same hardware scaling as the DW2.
- Resource usage: The factor 1/N discounts the intrinsic parallel speedup of an analog device whose hardware resources scale as N.The quantum component is estimated by comparing devices with the same hardware scaling.
V. PERFORMANCE OF D-WAVE TWO VERSUS SA AND SQA
The performance analysis compares optimizer-relevant quantiles and timing conventions across SA, SQA, and DW2 on finite-precision spin-glass instances. The studied methods show exponential-in-N total-time scaling, while DW2’s minimum annealing time limits interpretation of its observed slope.
- Benchmark metrics: Optimizer comparisons use high quantiles of time to solution because the hardest instances determine whether almost all problems can be solved.The selected high quantile is applied across all problem instances run on the optimizer.
- Timing measures: Wall-clock time includes device and algorithm overheads, whereas pure annealing time isolates the annealing component.Wall-clock time is relevant for applications, while pure annealing time is used for complexity-oriented comparisons.
- Problem instances: The instances use Chimera subgraphs with zero fields and coupling ranges from r = 1 to r = 7.Range r = 1 uses ±1 couplings and is less susceptible to calibration errors, while r = 7 has fewer degenerate minima but more calibration sensitivity.
- Scaling results: For sufficiently large N, SA, SQA, and DW2 total solution times scale as exp(cN).The observed DW2 slope is only a lower bound because its minimum annealing time exceeds the optimum for all tested sizes.
2. The ratio of quantiles
The paper measures speedup using ratios of corresponding time-to-solution quantiles across problem instances. For the DW2 benchmark, this comparison finds no limited quantum speedup at large problem sizes.
- Quantile-based benchmarking targets the fraction of instances solved, rather than experimentally identifying the hardest instance.The relevant quantile is selected according to the desired coverage of problem instances.
- The speedup quantity is the ratio of corresponding quantiles of classical and quantum time to solution.The paper uses quantiles because instance-dependent hardness makes worst-case identification impractical.
- At large N, the DW2-to-SA quantile speedup curves turn from positive to negative slope, indicating that SA eventually outperforms the DW2.This pattern occurs across quantiles and both ranges, except for the 50th quantile at r = 1.
- The reported speedup is an upper bound because the DW2 comparison uses fixed suboptimal annealing times.The DW2 annealing time is constrained to 20µs, the shortest possible time in the benchmark.
3. Wall-clock time
Wall-clock comparisons include device programming overhead in addition to annealing time. This overhead can obscure the scaling seen in pure annealing-time plots.
- The DW2 performs similarly to SA on a single classical CPU for sufficiently large problem sizes and high range values.The comparison uses wall-clock time to reach p = 0.99 over median-to-99th-hardness quantiles.
- The DW2’s large constant programming overhead masks the exponential increase in time to solution visible in pure annealing time.The wall-clock comparison uses 16 gauges for both r = 1 and r = 7.
1. Total time to solution
Instance-by-instance comparisons reveal heterogeneous performance between the DW2 and simulated annealing. Apparent pure-annealing advantages are reduced or disappear when wall-clock costs and gauge programming are included.
- The DW2 is sometimes up to 10× faster than SA in pure annealing time, but instance-level performance shows wide scatter.The pure annealing comparison averages over 16 DW2 gauges.
- Wall-clock advantages seen for some instances tend to disappear because programming multiple gauge choices penalizes the DW2.This penalty is absent from a comparison based only on pure annealing time.
- With 16 gauges, the DW2 solves most instances but is always slower than a classical CPU for r = 1.For r = 7, the DW2 is sometimes faster than a single classical CPU.
- Using one gauge, some r = 7 instances favor the DW2, while many instances are unsolved by the DW2.The figure marks unsolved DW2 instances separately from instances solved by SA.
2. Quantiles of ratio
The analysis tests for limited quantum speedup in subsets of instances by examining how quantiles of instance-by-instance time-to-solution ratios scale. Results differ by r and require caution because some instances use suboptimal annealing times.
- Quantile-based comparison: Quantile scaling is used to assess whether a subset of problem instances exhibits limited quantum speedup.The comparison focuses on ratios of individual instances’ time to solution rather than absolute times.
- Results by r: For r = 7, all quantiles bend downward at sufficiently large N, providing no evidence of limited quantum speedup.
- Qualification: The apparent r = 1 speedup should not be treated as solid evidence because its contributing instances were not run at optimal annealing times.
- Results by r: For r = 1, higher-than-median quantiles show some indication of limited quantum speedup relative to SA.
- Qualification: Establishing whether the r = 1 result persists requires testing instances with annealing times known to be optimal.
E. Arguments for and against a speedup on the DW2
The paper examines whether apparent DW2 speedup can survive scrutiny of annealing-time choices and instance subsets. Its arguments support a slowdown conclusion in one analysis, while leaving the high-quantile r = 1 result unresolved.
- Annealing-time effects: The apparent r = 1 speedup must be treated cautiously because the analysis uses suboptimal annealing times.
- Annealing-time effects: Assuming optimal annealing time grows with N, a crossover size N* exists where the optimal time reaches the fixed annealing time.This assumption is supported by simulated SA and SQA data and is considered plausible unless longer annealing becomes counterproductive through thermal-bath coupling.
- Annealing-time effects: Because S(N*) = Sopt(N*) and observed S(N) decreases with N, the slowdown conclusion also holds for optimal annealing times over a range of sizes.
- Instance-by-instance comparison: For the high-quantile r = 1 subset, the instance-by-instance comparison does not establish whether the limited speedup persists at larger sizes or optimal annealing times.
VI. DISCUSSION
Quantum speedup must be defined and measured according to the comparison, scaling, and instance-distribution question being asked. In the DW2 benchmark, whole-dataset analysis found no limited quantum speedup, while subset comparisons remained potentially artifactual or inconclusive.
- Definitions: Strong or provable quantum speedup is elusive, so the paper defines limited quantum speedup relative to corresponding classical algorithms solving the same task.The comparison can involve a quantum annealer and a classical annealing algorithm.
- Assessment challenges: Exponential speedup is easiest to define, whereas unknown or polynomial speedup requires matched hardware resources to avoid masking or faking quantum speedup.Parallel speedup can otherwise be mistaken for, or hide, quantum speedup.
- Assessment challenges: Finite-size scaling should emphasize the execution-time component dominant at large N, while both devices must be operated non-suboptimally.The example focuses on pure annealing time rather than total wall-clock time.
- Benchmark interpretation: Randomized benchmarks use ratios of high time-to-solution quantiles, whereas subset searches use quantiles of instance-by-instance time-to-solution ratios.The appropriate quantity depends on whether the goal is overall device performance or speedup for some instances.
- Benchmark interpretation: The DW2 showed no limited quantum speedup relative to simulated annealing across the benchmark set, while a subset comparison suggested possible speedup for some instances.The subset result may reflect excessively long DW2 annealing times for smaller instances.
- Open questions: The absence of clear speedup may reflect the problem class, noisy hardware, calibration errors, error correction, or speedup appearing in other problem classes.Future studies aim to identify instances with unambiguous speedup over classical hardware.
METHODS
The methods compare D-Wave Two with simulated classical and quantum annealing on Chimera-graph Ising problems. They specify device structure, annealing schedules, repetition-based success measures, calibration handling, and resource-matched timing analyses.
- Annealing methods: Simulated annealing lowers temperature in Monte Carlo updates of the Ising model and repeats runs to seek the global minimum.Each run ends in a local minimum at low temperature.
- Annealing methods: Quantum annealing maps Ising variables to Pauli z matrices and adds a transverse magnetic field in the x direction to induce quantum fluctuations.The resulting Hamiltonian is time dependent.
- Annealing schedules: The annealing schedule starts with B(0)=0 and a dominant transverse field, then increases B(t) while decreasing A(t), ending with A(t_a)=0.The temperature is held constant during the schedule.
- Annealing methods: Simulated quantum annealing uses path-integral quantum Monte Carlo, typically with 64 imaginary-time slices and cluster updates, while linearly changing the couplings.It samples world-line configurations rather than evolving an open quantum system.
- Device and instances: The ideal 512-vertex Chimera graph has treewidth 33, enabling dynamic programming whose runtime scales exponentially with treewidth.The general graph has N=2cL^2 vertices for an L × L grid of K_c,c cells.
- Annealing schedules: The DW2 implements a time-dependent Hamiltonian with device-specific transverse fields, and the experiments use the minimum annealing time t_a=20 µs.Engineering restrictions and control-line filtering affect the implemented schedule.
- Timing and programming: The device is programmed with couplings, local fields, repetition count, annealing time, and additional parameters contributing to wall-clock time.Wall-clock timing includes programming, cooling, annealing, readout, and communication.
- Device and instances: The DW2 Vesuvius chip contains an 8 × 8 lattice of eight-qubit cells, with 503 of 512 qubits and their couplers functional in the tested device.Scaling uses rectangular Chimera sub-lattices restricted to functional qubits.