Source-linked AI summary
Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
Helmut G. Katzgraber, Firas Hamze, Zheng Zhu, Andrew J. Ochoa, H. Munoz-Bauza
TL;DR
Detecting quantum speedup remains difficult on the small, noisy D-Wave Two device. The paper designs tunable hard spin-glass benchmarks and compares quantum annealing with classical simulated annealing; the device is generally slower at finding ground states, though some potential advantages are suggested.
Problem
Noise and the small number of qubits on the DW2 device make it difficult to detect quantum speedup.
Source: §V · p. 8Method
The paper uses spin-glass insights to design tunable hard instances and compares how instance complexity affects quantum annealing and classical approaches.
Source: §I · p. 2Results
DW2 is systematically slower at finding ground states for most studied disorder types, while classically hard spin-glass problems also seem typically hard for the quantum annealer.
Source: §VI · p. 9Takeaways & Limitations
Carefully designed spin-glass benchmarks can be considerably harder than previous attempts and tunable for studying performance across instance complexity.
Source: §I · p. 2, §V · p. 8Noise and the small number of qubits on DW2 make quantum-speedup detection difficult at present.
Source: §V · p. 8
Abstract
from arXiv · showhide
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a "`quantum advantage" over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.
I. INTRODUCTION
Quantum annealing has raised hopes of optimization advantages, but quantum speedup remains elusive. This paper proposes tunable, hard spin-glass benchmarks to compare how quantum and classical methods respond as instance complexity increases.
I. INTRODUCTION
- Quantum speedup remains undetected, with small devices, fragile quantum states, and benchmark choice all cited as possible obstacles.Current devices have at most 512 qubits, and the native Chimera spin-glass benchmark may be too easy or favor thermal approaches.Source: §I · pp. 1–2
- The proposed benchmark strategy designs hard, tunable instances on the native device to use as many available qubits as possible.Embedding harder problems reduces the number of logical qubits, while designing instances around device limitations is more tractable.Source: §I · p. 2
- Instance complexity is varied within a disorder type, and performance loss is compared across classical and quantum approaches.The spin-glass order-parameter distribution serves as a proxy for landscape features while ground-state degeneracy is kept ideally at one or as low as possible.Source: §I · p. 2
- The study does not attempt scaling analysis because accessible system sizes are considered too small to reach the asymptotic limit.The authors cite strong finite-size scaling corrections in prior simulations with about 10^3 spins.Source: §I · p. 2
- The DW2 is outperformed by state-of-the-art classical algorithms at finding ground states, though it may have an advantage on some carefully designed problems, especially with reduced noise.The device may also be more effective than simulated annealing at generating low-lying states in some cases.Source: §I · p. 2
II. NATIVE BENCHMARK: SPIN GLASSES
The paper uses an Ising spin glass on the DW2 Chimera topology as its native benchmark. It then proposes designing hard instances by tuning interactions on that native graph.
II. NATIVE BENCHMARK: SPIN GLASSES
- The native benchmark is an Ising spin glass defined on the DW2's Chimera topology.The study sets all local fields to zero and defines Ising spins on the lattice vertices, coupled along its edges.Source: §II · pp. 2–3
III. DESIGNING HARD INSTANCES
- Finite-temperature-transition spin glasses are difficult to embed because the physical-qubit overhead leaves only small logical systems, far from the asymptotic regime.The native Chimera spin glass instead has a zero-temperature phase transition, and its small-system energy landscape may be relatively simple for annealing approaches.Source: §III · p. 3
- The proposed alternative is to design interactions on the native Chimera graph to make problems as hard as possible for optimization approaches.The paper's roadmap uses spin-glass insights to produce tunable hard instances.Source: §III · p. 3
A. Problems with current approaches
The paper identifies limitations in existing benchmarks and proposes tunable spin-glass instances to compare how algorithms respond as instance complexity changes. It uses the overlap distribution P(q) to classify energy-landscape features, while seeking instances with a unique ground state.
A. Problems with current approaches
- For devices up to 512 variables, U1 and Uk benchmarks can have highly degenerate ground states, motivating instances designed to have a unique minimizing configuration.U1 uses bimodal couplers and Uk uses integer-valued couplers; the passage says these choices yield benchmarks too simple to challenge optimization approaches at these sizes.Source: A. Problems with current approaches · p. 3
- Cluster problems favor DW2 over classical codes when cluster Monte Carlo updates are disallowed, but adding such moves gives classical approaches the upper hand.The authors reject this route as a speedup benchmark because the moves are unphysical.Source: A. Problems with current approaches · p. 3
B. Designing tunable hard instances
- P(q) structure offers an approximate hardness signal: support near q = 0 correlates with longer autocorrelation times, and peak separation corresponds roughly to barrier thickness; barrier-height correspondence remains untested.The authors report confidence in the peak-distance relationship but say the depth relationship needs more precise experimental testing.Source: B. Designing tunable hard instances · p. 4
- The design uses coupler magnitudes from a Sidon set to reduce zero local fields, which otherwise multiply ground-state degeneracy by 2^k when k spins have zero fields.The passage gives {2, 5, 10} as a Sidon set and contrasts it with {2, 5, 7}.Source: B. Designing tunable hard instances · p. 4
- The authors generate random problems, retain instances with one ground-state configuration, and divide them into subclasses using normalized P(q).They illustrate the approach with interactions from S28, normalized to lie between ±1.Source: B. Designing tunable hard instances · p. 4
- Thick-barrier instances have P(q) > 5 for |q| ≤ 0.75 and are expected to challenge both simulated and quantum annealing.The authors expect these instances to be among the hardest on average, based on classical simulations.Source: B. Designing tunable hard instances · pp. 4–5
- Thin-barrier instances have little support for |q| ≤ 0.5 and multiple peaks beyond that range; simulated annealing is expected to struggle, while quantum annealing might benefit if it has an advantage.They are expected to be hard on average, but less hard than thick-barrier instances.Source: B. Designing tunable hard instances · p. 5
- Small-barrier instances have P(q) < 0.1 for |q| ≤ 0.75 and a landscape with one dominant valley, so the authors expect them to be easiest for annealing approaches.Their overlap distribution is described as resembling a low-temperature ferromagnet.Source: B. Designing tunable hard instances · p. 5
IV. RESULTS
The authors calibrate simulated annealing sweeps against DW2 on bimodal disorder and use average success probabilities to compare performance, since medians can be zero for the hardest DW2 instances.
IV. RESULTS
- 900 sweeps make the average success probabilities of simulated annealing and DW2 approximately equal for bimodal disorder, providing the chosen baseline calibration.The simulated annealing sweep count is tuned for an approximately fair comparison with a known baseline study.Source: §IV · p. 5
- Average success probabilities are reported because DW2 often fails to find minima in the hardest classes, making its median success probability zero.The authors note that probabilities remain well-defined as averages because they lie between 0 and 1.Source: §IV · p. 5
- The comparison focuses mainly on average success probabilities rather than medians, which can be uninformative for the hardest DW2 classes.The passage states that the device often cannot minimize the cost function within the performed runs for those classes.Source: §IV · p. 5
A. The ugly—D-Wave Two fails often
Across the tested instance classes, DW2 shows increasing difficulty and often fails on harder problems, while simulated annealing distinguishes bimodal disorder as easier but does not separate thin- from thick-barrier instances. With optimized sweep counts, simulated annealing can outperform DW2 across all studied disorder classes.
A. The ugly—D-Wave Two fails often
- Bimodal disorder is considerably easier for simulated annealing than the other classes, while DW2 shows a clear complexity progression and success probabilities below 10^-4 on many harder problems.For the tested sweep count, U4 has complexity similar to S28 instances with small or no barriers.Source: A. The ugly—D-Wave Two fails often · p. 6
- Simulated annealing does not distinguish S28 thin- and thick-barrier instances, whereas DW2 does.For the DW2 device, the hardest classes often have median success probability zero, while simulated annealing has finite median probabilities across a wider range of instances.Source: A. The ugly—D-Wave Two fails often · p. 6
- Optimizing simulated-annealing sweeps lets those codes outperform DW2 across every disorder class studied.The authors also report that simulated annealing solves a wider range of instances.Source: A. The ugly—D-Wave Two fails often · p. 6
- The double-peaked success pattern is presented as evidence of quantum behavior in earlier work, but its interpretation has been challenged by quasiclassical models.The passage cites Refs. for the evidence claim and Refs. [59] [60] for the challenge.Source: A. The ugly—D-Wave Two fails often · p. 6
B. The bad—Previous instance classes are too easy
Success probabilities distinguish the instance classes differently on the DW2 and simulated annealing (SA): U1 is comparatively easy, while the Sidon S28 classes challenge the device. With SA sweeps calibrated on U1, classical codes outperform the DW2 on all studied S28 classes.
B. The bad—Previous instance classes are too easy
- For every studied S28 class, classical SA simulations outperform DW2 on raw average success probability.SA sweeps were chosen so U1 average success probabilities were comparable to DW2; the reported SA-to-DW2 ratios also favor SA across S28.Source: B. The bad—Previous instance classes… · p. 6, Figure 4 · p. 7
- U1 average success probabilities are about one order of magnitude higher than those for other disorder classes, making highly degenerate problems too easy for detecting speedup.The figure caption attributes U1's ease as a possible consequence of degeneracy.Source: B. The bad—Previous instance classes… · p. 6, Figure 3 · p. 7
- DW2 difficulty progresses from U1 through U4 and S28 with no dominant barriers to S28 with thin and thick barriers.SA finds U4 comparable to S28 without dominant barriers, and its average success probabilities are approximately the same for thin- and thick-barrier S28 instances.Source: B. The bad—Previous instance classes… · p. 6, Figure 2 · p. 6
- For DW2, S28 classes have far lower average success probabilities, consistent with noise perturbing problems whose gap to the first excited state is small.The authors compare relative probabilities within instance types to help filter noise effects.Source: B. The bad—Previous instance classes… · p. 6
C. The good—Evidence of a quantum advantage?
For Sidon instances, reducing barrier thickness improves DW2 average success probabilities while producing no average improvement for classical algorithms. This suggests possible quantum advantage for thin, tall barriers, but the authors say stronger, more systematic study is needed.
C. The good—Evidence of a quantum advantage?
- Reducing barrier thickness improves DW2 average success probabilities, while classical algorithms show no average effect; removing dominant barriers improves both.The authors caution that the possible advantage for thin, tall barriers needs a more careful and systematic study.Source: C. The good—Evidence of a quantum… · p. 7, Figure 5 · p. 7
- Including more low-lying S28 energy levels raises DW2 success probabilities more markedly than SA, indicating noise affects ground-state detection.Including the lowest 10 energy levels corresponds to less than a 1% increase in overall system energy; averaging over gauges also helps DW2.Source: C. The good—Evidence of a quantum… · pp. 7–8
- For problems affected by device noise, DW2 might efficiently deliver low-lying energy states, with possible relevance to machine learning and Bayesian statistical analysis.The paper suggests exploring error-correction and hybrid approaches for optimization.Source: C. The good—Evidence of a quantum… · p. 8
V. DISCUSSION
The discussion identifies coupler noise as a possible source of poor DW2 performance on fragile spin-glass instances. Tests with a larger classical energy gap show qualitatively similar results, while the device's trends across low-lying levels also suggest noise may dominate.
V. DISCUSSION
- The authors frame carefully designed spin-glass benchmarks as important for assessing speedup, while noting that noise and limited qubit counts currently impede its detection.They identify native problems using as many device qubits as possible as a way to avoid embedding overhead.Source: §V · p. 8
A. Effects of coupler noise
- DW2 success probabilities across low-lying energy levels for S28 suggest that noise might dominate the device's overall poor performance.Figure 6 compares average success probabilities against the number of levels above the ground state, with U1 and U4 in the top panel and S28 below.Source: Figure 6 · p. 8
- Spin-glass states are fragile: small coupler perturbations can destroy the state or change the problem, and rare large-domain flips can affect experiments.Multiple gauges may alleviate this only slightly; increasing the classical gap beyond machine noise can partially reduce the effects, at the cost of easier benchmarks.Source: A. Effects of coupler noise · p. 8, §V · p. 8
- The larger-gap Sidon set {±5, ±6, ±7} yields qualitatively similar results to the tested instances.This addresses the concern that the minimum Sidon gap, ΔE = 2/28, is too small relative to machine encoding restrictions.Source: A. Effects of coupler noise · pp. 8–9
B. Effects of local-field noise
The authors note that longitudinal fields can affect spin-glass states, making intrinsic qubit noise a plausible contributor to lower success probabilities. In their overall conclusion, DW2 is systematically slower than state-of-the-art classical SA for most studied disorder types.
B. Effects of local-field noise
- Longitudinal random fields can strongly affect spin-glass states, so intrinsic DW2 qubit noise might reduce success probabilities by perturbing the system and dominant barriers.The passage notes that the de Almeida-Thouless line's existence for short-range spin glasses remains debated, while numerical evidence supports field sensitivity across geometries.Source: B. Effects of local-field noise · p. 9
VI. SUMMARY AND CONCLUSIONS
- For most studied disorder types, DW2 is systematically slower at finding ground states than state-of-the-art classical SA codes.Optimizing SA sweeps lets the classical codes outperform DW2 for all studied disorder classes.Source: §VI · p. 9
- The authors say better calibration, noise reduction, schedule optimization, larger systems, and tailored spin-glass problems might help the search for quantum speedup.The conclusion also notes that it remains unclear whether the suggested thin-barrier effect persists at larger problem sizes.Source: §VI · p. 9
Appendix A: D-Wave Two quantum annealer description
The DW2 seeks the ground state of an Ising problem on the Chimera graph by slowly applying and removing a transverse field. Its annealing schedule and gauge-based success measurement define the device protocol used in this study.
Appendix A: D-Wave Two quantum annealer description
- DW2 targets the ground state of an Ising problem on the Chimera graph by slowly applying and removing a transverse field.The time-dependent Hamiltonian combines driver and problem Hamiltonians, whose relative magnitudes change over the anneal.Source: Appendix A · p. 9
- The annealing schedules plot A(s) and B(s), the relative driver- and problem-Hamiltonian magnitudes, against normalized time s.A(s) decreases and B(s) increases, with s = t/tf.Source: Appendix A · p. 9, Figure 8 · p. 10
- The chip has 496 working qubits; its diagram distinguishes fully functional, working-with-missing-couplers, and broken qubits.Circles denote qubits and lines denote couplers.Source: Figure 7 · p. 10
1. D-Wave Two Methodology
- Each instance is run 10^4 times in 10 randomly gauged batches to protect against parameter noise and control errors.Although gauge transformations do not fundamentally change the problem, device noise makes each transformed instance correspond to a different Hamiltonian in practice.Source: §1 · p. 10
- Instance success probability across gauges is derived from the geometric mean of gauge failure rates; success can mean reaching the ground state or an energy within Δ of it.The device uses autoscaling to use the allowed range of nominal J and h parameters.Source: §1 · p. 10
2. Simulated annealing methodology
The simulated-annealing comparison uses an optimized Chimera-compatible code and fixed run counts. Its sweep count is calibrated so average success probabilities match DW2 on the commonly studied bimodal disorder baseline.
2. Simulated annealing methodology
- The SA code uses a Chimera-topology optimization that exploits bipartiteness to halve simulated variables and improve performance over plain SA.The study uses the authors’ an ss ge nf bp vdeg routine.Source: §2 · p. 10
- Each instance receives 10^4 runs of 900 Monte Carlo sweeps, using the default geometric schedule with instance-class-specific temperature scales.The parameters by disorder class are listed in Table I.Source: §2 · p. 10, Table I · p. 11
- They chose Nsw = 900 so DW2’s average success probabilities agreed with simulated annealing for commonly studied bimodal (U1) disorder, providing a baseline for other instance classes; 2,000-sweep simulations showed qualitatively similar results.Source: §2 · p. 10
Appendix B: Parallel tempering Monte Carlo simulation details
The parallel-tempering simulations estimate overlap distributions for disorder instances using replica exchange and isoenergetic cluster moves. The appendices describe success-probability results for studied and additional instance classes, while noting that some classes were too easy or difficult to characterize with unique ground states.
Appendix B: Parallel tempering Monte Carlo simulation details
- For each problem class, 10^5 disorder instances are analyzed using two 496-spin replicas, 30 temperatures, and parallel tempering with isoenergetic cluster moves.The lowest temperature is 0.212; 223 Monte Carlo sweeps are used for thermalization and another 223 for measuring P(q).Source: Appendix B · p. 11
Appendix C: Experimental Results
- Table II reports average success probabilities and numbers of disorder instances for the studied classes, with averages jackknifed over instances.The supplied passage does not give the table’s cell values.Source: Appendix C · p. 11
Appendix D: Other Instance Classes Studied
- Additional instance classes were either too easy or yielded too few unique ground states; J4 and S1,3,7 instances were limited to fewer than 32 minimizing configurations.Their average success probabilities and instance counts are listed in Table III.Source: Appendix D · p. 11, Table III · p. 11