PaperlayerView exact revision on arXiv

Source-linked AI summary

Demonstration of a scaling advantage for a quantum annealer over simulated annealing

Tameem Albash, Daniel A. Lidar

arXiv:1705.07452v3quant-ph

TL;DR

Experimental quantum-annealing benchmarks lacked verified optimal annealing times, limiting conclusions about scaling advantages. The paper introduces suitable problem instances, enables optimal-TTS comparisons on D-Wave hardware, and finds better scaling than simulated annealing but worse scaling than simulated quantum annealing.

  • Problem

    Experimental quantum-annealing studies lacked complete optimal-TTS assessments because optimal annealing times could not be verified.

  • Method

    The paper constructs logical-planted instances combining frustrated loops with small tunneling gadgets and benchmarks D-Wave hardware against SA, SVMC, and SQA.

  • Results

    The D-Wave device shows a certifiable scaling advantage over simulated annealing, while SQA has the best scaling among the tested annealing algorithms.

  • Takeaways & Limitations

    Verifiably optimal annealing-time instance classes enable more definitive scaling assessments of current and future quantum annealers.

Abstract

from arXiv · show

The observation of an unequivocal quantum speedup remains an elusive objective for quantum computing. The D-Wave quantum annealing processors have been at the forefront of experimental attempts to address this goal, given their relatively large numbers of qubits and programmability. A complete determination of the optimal time-to-solution (TTS) using these processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here we overcome this obstacle and present a class of problem instances for which we observe an optimal annealing time using a D-Wave 2000Q processor over a range spanning up to more than $2000$ qubits. This allows us to perform an optimal TTS benchmarking analysis and perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing. We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with $95\%$ confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.

I. INTRODUCTION

The paper addresses the difficulty of demonstrating quantum speedup experimentally by introducing problem instances that enable complete scaling analysis of a D-Wave quantum annealer. It finds a certifiable scaling advantage over simulated annealing, while simulated quantum annealing scales better than the hardware.

  • Motivation: Quantum annealers provide programmable devices with thousands of noisy qubits for combinatorial optimization, unlike universal gate-model quantum computers.They implement physical quantum annealing using programmable qubit-qubit interactions.
  • Motivation: The central benchmarking obstacle was the inability to identify an optimal annealing time for experimental quantum annealers.Without optimality, scaling conclusions can be incomplete or misleading.
  • Approach: A new logical-planted instance class enables complete scaling analysis of the D-Wave 2000Q across problem sizes exceeding 2000 spins or qubits.The construction combines frustrated cycles across the hardware graph with small tunneling gadgets.
  • Results: The study certifies an algorithmic scaling advantage for quantum-annealing hardware over single-spin simulated annealing.Earlier analyses could certify disadvantages but not advantages without verified optimal annealing times.
  • Results: Simulated quantum annealing has the best scaling among the tested annealing algorithms and outperforms the quantum-annealing hardware.SQA and SVMC are used to investigate tunneling, with SQA more closely modeling quantum annealing than simulated annealing.

II. OPTIMAL TIME-TO-SOLUTION

The paper defines time-to-solution benchmarking around success probability, repeated runs, ensemble quantiles, and an empirically verified optimal annealing time. A new instance class makes complete optimal-TTS scaling possible on D-Wave processors.

  • TTS metric: Time-to-solution measures the time required to find the ground state at least once with a desired probability.The metric captures a tradeoff between long high-success runs and repeated shorter runs.
  • TTS metric: The TTS calculation combines runtime, required repetitions, instance size, and device capacity through a parallel-utilization factor.The required repetitions depend on single-run success probability, while N/Nmax accounts for maximal parallel utilization.
  • Optimality: For random instance ensembles, performance is evaluated using a chosen quantile of the TTS distribution at each problem size.The quantile is solver-dependent and is optimized over annealing time.
  • Optimality: If the optimal annealing time lies below the hardware minimum, the optimal TTS cannot be determined and suboptimal timing can distort scaling comparisons.This was the critical obstacle in earlier experimental benchmarking studies.
  • Hardware results: The reported instance class has an optimal annealing time greater than tmin = 5µs on the D-Wave 2000Q.Results are also provided for the D-Wave 2X, whose largest energy scale is approximately 40GHz.
  • Hardware results: This enables the first complete optimal-TTS scaling results for an experimental quantum annealer.The analysis is defined using scaling obtained from certifiably optimal annealing times.

III. RESULTS

The results section presents evidence for optimal annealing times and a scaling advantage of a physical quantum annealer over simulated annealing, alongside disadvantages relative to SQA and SVMC. It then describes the instance construction and tunneling mechanism.

  • III. RESULTS: The results establish evidence for optimal annealing times and a scaling advantage of a physical quantum annealer over simulated annealing.The section also compares the hardware with SQA and SVMC.
  • III. RESULTS: The section describes the problem-instance construction and examines tunneling as an explanation for the observed algorithmic behavior.These analyses follow the benchmarking results.

A. Evidence for optimal annealing times

The logical-planted instances exhibit accessible optimal annealing times, enabling complete optimal-TTS scaling comparisons across the tested solvers. The D-Wave hardware scales better than simulated annealing but worse than SQA and, in several settings, SVMC.

  • Evidence for optimal annealing times: At L = 16, a representative logical-planted instance has a clear optimal annealing time of t* = 50µs.The TTS minimum identifies the optimum for this instance.
  • Evidence for optimal annealing times: For L ≥ 12, the median TTS has an identifiable minimum whose optimal annealing time shifts to larger annealing times as problem size increases.The shift is consistent with the increasing number of instances having larger per-instance optimal annealing times.
  • Scaling comparisons: 95% confidence supports a DW2KQ scaling advantage over SA across the full quantile range [0.25, 0.9].The comparison uses the complete optimal-TTS analysis for the logical-planted instances.
  • Scaling comparisons: SQA outperforms DW2KQ at both β = 2.5 and β = 0.51 across all quantiles, ruling out an unqualified quantum speedup.SVMC also outperforms DW2KQ at β = 0.51 and at β = 2.5 except q = 0.9, where the error bars are too large for significance.
  • Robustness: The results remain robust when the SA schedule changes from quadratic to linear in β and when the quantile-of-ratios speedup metric is used.These robustness checks are reported for the benchmarking conclusions.

C. Construction of problem instances with an optimal annealing time

The instance construction targets two properties needed for benchmarking: a known ground-state energy and an optimal annealing time on D-Wave processors.

  • Construction goals: The construction guarantees knowledge of the ground-state energy for the generated problem instances.A known ground-state energy is useful for benchmarking optimizers at ever-growing problem sizes.
  • Construction goals: The construction is designed to produce an optimal annealing time on D-Wave processors.This property enables the optimal-TTS analysis described earlier in the paper.
  • Construction goals: These two properties define the target behavior of the problem instances used in the study.The passage presents them as the two key desired properties.

1. Planted solutions

Planted-solution instances are built from frustrated loops on the logical hardware graph, with ferromagnetic intra-cell couplers preserving the planted solution on the physical graph.

  • Planted solutions: The construction builds the problem Hamiltonian as a sum of frustrated loop Hamiltonians H_l.The planted solution is the simultaneous ground state of all loop terms.
  • Planted solutions: The Hamiltonian is frustration-free, so the planted solution is also the ground state of the full problem Hamiltonian.The planted solution can be chosen as the all-zero configuration.
  • Logical graph: Planted solutions are defined on complete logical unit cells of the D-Wave hardware graph, which form a square lattice for an ideal Chimera graph.Logical couplings are imposed only where all four physical inter-cell couplings are available.
  • Logical graph: Ferromagnetic intra-unit-cell couplers ensure that the logical planted solution maps to the corresponding physical-spin configuration.All physical spins within each unit cell are set to their corresponding planted values.

2. Gadgets

The gadget augmentation is motivated by the need to create an optimal annealing time and is implemented with eight-qubit gadgets placed randomly across selected unit cells.

  • Gadget motivation: The construction seeks an optimal annealing time by exploiting competition between annealing dynamics in weakly coupled systems and the thermal environment.Earlier planted-solution instances had TTS rising monotonically with annealing time.
  • Gadget construction: Eight-qubit gadgets are placed in randomly chosen unit cells comprising a fraction p = 0.1 of the complete unit cells.The gadget fits within a D-Wave unit cell.
  • Gadget construction: The gadget’s all-zero ground state preserves the all-zero ground state of the full Hamiltonian.Its first excited state is doubly degenerate and has average Hamming weight seven.
  • Scope of the construction: The gadget’s annealing properties are not generically expected to transfer to the full problem Hamiltonian, so their extent must be established for these instances.The passage explicitly frames this transfer as something demonstrated empirically below.

3. Tunneling

The 8-qubit gadget exhibits tunneling-like behavior identified through a sharp Hamming-weight reorientation near the minimum gap and contrasting SQA and SVMC responses. This behavior can persist when the gadget is embedded in larger planted-solution instances, although tunneling cannot be directly probed on the hardware.

  • A sharp change in ground- and first-excited-state Hamming weights coincides with the minimum energy gap, indicating a tunneling transition.The ground state reorients toward |0 ··· 0⟩, while the first excited state approaches |1 ··· 1⟩.
  • SVMC and SQA serve as proxies for tunneling analysis because exhaustive exploration of the multidimensional semiclassical energy landscape is infeasible.SVMC uses planar rotors, whereas SQA uses path-integral Monte Carlo.
  • SQA success probability increases as temperature decreases, whereas SVMC success probability decreases and becomes trapped in higher excited states.
  • The 8-qubit gadget is represented as a complete bipartite graph with unit-magnitude ferromagnetic and antiferromagnetic couplers and specified local fields.
  • The gadget’s tunneling properties can be inherited by planted-solution instances at the largest tested problem size, but hardware tunneling and temperature dependence remain inaccessible to direct measurement.

4. The gadget is responsible for the observed optimal annealing time

The gadget changes success-probability scaling in a way that produces an optimal annealing time. Its effect is linked to temperature-dependent differences between SQA and SVMC, while competing dynamical mechanisms may also contribute.

  • The gadget produces larger power-law scaling coefficients for success probability than instances without it, leading to an observed optimal annealing time.The comparison uses 100 logical-planted instances at L = 16 on the DW2KQ processor.
  • For the gadget alone, SQA improves as inverse temperature decreases, whereas SVMC rapidly deteriorates.
  • The scaling analysis fits ln pS to a ln tf + b over tf ∈ [5, 50] µs, the range where TTS decreases.
  • An optimal annealing time requires TTS ∝ tf/g(tf) to decrease over some range when pS(tf) = g(tf) ≪ 1.
  • Possible mechanisms include competition between adiabaticity and thermal excitations, or thermal relaxation that slows after the system enters a quasistatic regime.

IV. DISCUSSION AND OUTLOOK

The study establishes a scaling advantage of quantum-annealing hardware over simulated annealing, while finding that simulated quantum annealing scales substantially better than the hardware. It also identifies important scope limits and proposes instance-generation strategies for future analyses.

  • Scaling advantage: The demonstrated QA-hardware advantage over SA applies to frustrated-loop instances augmented with a tunneling gadget.The gadget uses eight qubits and has a small quantum gap on the order of the temperature.
  • Interpretation: SVMC also outperforms SA, indicating that the advantage may reflect more efficient thermal updates on a semiclassical energy landscape.The authors distinguish SA’s classical Ising landscape from the semiclassical landscape used by SVMC and transverse-field annealing.
  • Interpretation: SQA scales far better than SVMC and the DW2KQ, with its performance improving as simulation temperature decreases.SQA adds tunneling-like path-integral Monte Carlo updates to the thermal updates it shares with SVMC.
  • Interpretation: The DW2KQ’s advantage over SA alongside SQA’s stronger scaling suggests that the hardware dynamics may be predominantly classical with only a small quantum component.The authors explicitly describe this interpretation as speculative.
  • Temperature and noise: Higher temperatures degrade median and lower-percentile SVMC and SQA performance, while additional hardware noise may further disadvantage the DW2KQ.SVMC can improve at higher percentiles and temperatures, consistent with thermal barrier hopping.
  • Limitations: The tested instances are not necessarily computationally hard, and the study addresses finding any ground state rather than fair sampling of all ground states.The authors note that polynomial fits outperform exponential fits and that transverse-field annealing samples ground states in a biased manner.

Appendix B: The D-Wave quantum annealers

The appendices document the two D-Wave processors, their hardware and logical graphs, annealing schedules, timing considerations, and benchmarking visualizations. The analysis focuses on annealing time while noting that programming, initialization, and readout costs can dominate wall-clock runtime.

  • The DW2KQ provided 2023 functional qubits and 5874 programmable couplers, while the DW2X provided 1098 functional qubits and 3049 programmable couplers.
  • The minimum annealing time for the DW2KQ and DW2X was 5µs, and experiments used random gauges to reduce local-bias and precision-error effects.
  • The processors’ annealing schedules were computed from D-Wave flux-qubit models, with operating temperatures of 14.1mK for DW2KQ and 12.5mK for DW2X.
  • The logical and hardware graphs differ by processor generation, with subgraphs selected up to L ≤16 for DW2KQ and L ≤12 for DW2X.
  • For the logical-planted instances, SQA success probability was maximized using 64 Trotter slices, whereas 32, 128, and 256 slices were also tested.
  • The study reports annealing-time TTS rather than full wall-clock TTS because programming, initialization, and readout times can mask scaling.
  • Median quantile-of-ratios show positive slopes for SA and SVMC relative to DW2KQ, but a negative slope for SQA, indicating slowdown relative to DW2KQ.

Appendix C: Simulation Parameters and Timing

The appendices specify GPU implementations, schedules, timing models, and optimal-TTS fitting procedures for SA, SQA, SVMC, and the D-Wave benchmarks. They also document schedule robustness and limitations of the SQA Trotter-slice study.

  • SA: SA updates spins in Chimera unit cells using GPU-resident local fields and couplers to reduce global-memory access.
  • SA: SA uses fSA = 50ns−1 and a temperature schedule based on the DW2X schedule with β = 0.132.
  • SVMC: SVMC replaces spin configurations with angles θ_i and uses β = 2.5 for logical-planted instances and β = 0.51 for hardware-planted instances.
  • SQA: SQA uses 64 Trotter slices and Wolff cluster updates along imaginary time, with a randomly selected slice providing the final classical state.
  • SQA: Increasing Trotter slices reduced success probability in one checked instance, but testing this across more than 2000 qubits was computationally prohibitive.
  • Schedule robustness: Alternative SA schedules shifted the TTS curve without changing its scaling within statistical error bars, supporting robustness to minor schedule changes.
  • Optimality and comparison: Optimal TTS was obtained by fitting ln⟨TTS⟩ to a quadratic function of ln tf, with the fitted minimum defining t* and ln⟨TTS⟩*.

Appendix G: Gadget and Instance construction

The instance constructions combine planted-solution graphs with an eight-qubit gadget designed to probe device-specific behavior. The resulting classes exhibit accessible optimal annealing times and distinguish the scaling of hardware and classical solvers.

  • Gadget construction: The eight-qubit gadget fits within a D-Wave unit cell and has bipartite K4,4 connectivity with specified Ising fields and couplers.
  • Logical-planted instances: Logical-planted instances are built on the DW2KQ logical graph of complete unit cells, with loop-based planted solutions embedded using ferromagnetic intra-cell couplings.
  • Logical-planted instances: The gadget was placed in a fraction p = 0.1 of connected unit cells, producing Hamiltonians with |Jij| ≤6 while preserving the all-zero ground state.
  • Device comparison: The gadget’s success-probability peak occurred near 100µs on DW2X and near 300µs on DW2KQ, with peak positions robust across representative unit cells.
  • Hardware-planted instances: Hardware-planted instances use ⌊α8L2⌋ frustrated loops on the DW2KQ hardware graph with α = 0.35 and retain the all-zero ground state.
  • Hardware-planted instances: Hardware-planted instances show clear TTS minima for L ∈[8, 16], with the minimum moving to higher annealing times as problem size increases.
  • Optimal annealing times: Optimal annealing times increase with problem size, rise faster for DW2KQ than DW2X, and eventually flatten for both instance classes.
  • Scaling results: SQA has the smallest scaling coefficient for hardware-planted instances, while SQA also shows the best scaling among tested solvers for logical-planted instances.

Appendix H: Success probability scaling

The appendices examine success-probability fits, alternative solvers, and optimal-TTS comparisons. They find robust SA scaling, strong SQA performance, and different solver rankings across logical- and hardware-planted instances.

  • Success-probability scaling: For a representative logical-planted instance, ln(pS) agrees with power-law fits over tf ∈[5, 50]µs, both with and without the gadget.
  • Solver comparison: SQA remains the best-scaling tested algorithm for logical-planted instances and outperforms algorithms designed for the Chimera graph.
  • HFS: Optimizing HFS tree-update counts was necessary because its default stopping rule can be highly non-optimal, especially for hardware-planted instances.
  • HFS: For logical-planted instances, HFS scales better than DW2KQ, whereas for hardware-planted instances their scaling is statistically indistinguishable.
  • SAC: SAC performs simulated annealing with additional simultaneous unit-cell updates, using fSAC = 25ns−1.
  • MWPM: MWPM’s success probability decreases with problem size because the gadget selects a subset of ground states, causing MWPM to predominantly choose the wrong ground state.
  • Optimal-TTS fitting: The optimal-TTS analysis fits each solver’s ln⟨TTS⟩ data to a quadratic in ln tf, extracting the optimal annealing time and corresponding TTS.
Loading 1705.07452v3…