PaperlayerView exact revision on arXiv

Source-linked AI summary

Probing for quantum speedup in spin glass problems with planted solutions

Itay Hen, Joshua Job, Tameem Albash, Troels F. Rønnow, Matthias Troyer, Daniel Lidar

arXiv:1502.01663v3quant-phcond-mat.stat-mech

TL;DR

The paper asks whether quantum annealing can provide a speedup on optimization problems beyond existing classical methods. It constructs frustrated Ising benchmarks with planted solutions and tunable hardness, then compares D-Wave Two with several classical algorithms. DW2 shows no speedup on the hardest, most frustrated instances, while a speedup remains possible for easier, less frustrated cases, within the studied scope.

  • Problem

    Conclusive experimental evidence for quantum speedup in optimization remained unavailable, motivating tests against strong classical algorithms on controlled problem instances.

  • Method

    The paper constructs frustrated Ising problems around planted ground states with tunable hardness and compares DW2 with classical algorithms using scaling and speedup analyses.

  • Results

    DW2 shows worse scaling than classical algorithms for lower clause densities, while a potential speedup remains possible at higher clause densities, especially α ≥0.4 against HFS.

  • Takeaways & Limitations

    Planted-solution benchmarks provide a tool for locating where this DW2 processor does not or might exhibit speedup on frustrated Ising problems.

  • Takeaways & Limitations

    The paper identifies harder problems, reduced decoherence and control noise, error correction, and theoretically validated problem classes as needed before conclusive quantum-speedup demonstrations.

Abstract

from arXiv · show

The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.

I. INTRODUCTION

The paper addresses the unresolved question of whether quantum annealers can provide a scaling advantage for optimization, despite progress in quantum hardware. It introduces tunable, frustrated Ising problems with planted ground states to test the D-Wave Two against classical methods.

  • Motivation: Quantum speedup would mean solving some computational problems with better scaling than classical methods using quantum effects.The paper notes that conclusive experimental evidence for quantum speedup was not yet available.
  • Motivation: The study compares the D-Wave Two with classical algorithms, including simulated classical and quantum annealing methods.Technical constraints required operating the putative quantum annealer in a suboptimal regime.
  • Contribution: The benchmark problems use frustration to create classically hard optimization instances with tunable hardness.This extends earlier random spin-glass studies by controlling hardness and specifying at least one known ground state.
  • Device: The D-Wave device evolves from a known transverse-field ground state toward a classical Ising-model cost-function ground state.The classical Hamiltonian is defined on the D-Wave Chimera hardware graph.
  • Device: The Ising model uses programmable couplings and local longitudinal fields on superconducting flux qubits arranged on the Chimera graph.The spin variables may be classical Ising spins or Pauli spin-1/2 matrices.

II. FRUSTRATED ISING PROBLEMS WITH PLANTED SOLUTIONS

The benchmark generator builds frustrated local Ising clauses around a known planted solution and combines them into instances whose hardness can be tuned through clause construction. The planted state remains a ground state while frustration and overlap produce varied difficulty.

  • Problem construction: The method generates frustrated Ising benchmark families with tunable hardness by adjusting the amount of frustration.Frustration can cause classical algorithms to become trapped in local minima.
  • Problem construction: Each problem Hamiltonian is formed by summing M local Ising Hamiltonians defined on Chimera subgraphs, whose clauses may partially overlap.Clause size does not scale with the overall problem size.
  • Problem construction: A planted solution is chosen before constructing local Hamiltonians, and each clause is designed so that the corresponding planted-spin assignment minimizes it.The planted solution is therefore a simultaneous ground state of all local Hamiltonians.
  • Loop clauses: Random loops on the Chimera graph provide the local clauses, with loop couplings assigned so the planted solution minimizes each clause.The construction begins with a random planted configuration and random loop generation.
  • Frustration: Flipping one coupling sign on a loop makes the clause frustrated while preserving the planted solution as a ground state.Adding overlapping clauses can cancel some frustration and contribute to an easy-hard-easy pattern.
  • Benchmarking properties: Knowing a ground-state configuration enables direct frustration measurements and avoids expensive exact verification of the ground-state energy.The paper reports that frustration measures correlate with hardness defined through success probability or scaling.

III. ALGORITHMS AND SCALING

The evaluation compares DW2 with several classical and quantum-inspired algorithms using probabilistic success and time-to-solution measures. Across solvers, hardness varies nonmonotonically with clause density, while frustration peaks near the hard regime.

  • Algorithms: The comparison includes simulated annealing, simulated quantum annealing, SSSV, and the Chimera-specialized HFS algorithm.HFS is specifically designed to exploit the treewidth scaling of the Chimera graph.
  • Evaluation: Success probability is estimated from repeated runs across many instances, and time-to-solution combines the required repetitions with run duration.For DW2, duration is the annealing time; for simulated methods, it is sweeps multiplied by time per sweep.
  • Evaluation: SAA records only the final annealing energy, whereas SAS retains the lowest energy encountered during the schedule.The annealer mode is intended to more faithfully model an analog annealing device.
  • Hardness versus clause density: TTS exhibits a clear peak near α = 0.17 ± 0.01 for HFS, consistent with the DW2 peak across Chimera subgraph sizes.The plotted TTS uses q = 0.5 and a logarithmic scale.
  • Hardness versus clause density: Frustration fraction has a broad peak at α ≈0.25, near the clause density expected to produce the hardest instances.The measure is the fraction of frustrated couplings relative to all couplings, averaged over 100 instances for each α and N.
  • Scaling: The benchmark size is parameterized by the Chimera subgraph scale L, with N = 8L^2 spins and λ = {L, α, q}.Dynamic programming scales exponentially in the Chimera graph treewidth.

IV. PROBING FOR A QUANTUM SPEEDUP

The paper distinguishes limited speedup against annealing-like classical algorithms from potential speedup against HFS. This comparison is intended to test whether DW2 has a scaling advantage on the frustrated benchmark set.

  • Speedup definitions: The study probes for limited or potential quantum speedup on the frustrated planted-solution Ising problems.The terminology separates comparisons with annealing-like algorithms from comparisons with HFS.
  • Speedup definitions: Limited speedup is defined through comparisons with SA, SQA, and SSSV.These algorithms implement approaches similar to quantum annealing on classical hardware.
  • Speedup definitions: Potential speedup is defined through comparison with HFS, which does not implement a similar algorithmic approach to a quantum annealer.HFS is treated separately because it is a specialized classical algorithm for the Chimera graph.

A. Dependence on clause density

Hardness varies nonmonotonically with clause density: the studied instances follow an easy-hard-easy pattern, while frustration and time-to-solution peak in nearby intermediate-density regimes. The figures compare solver scaling, speedup-ratio slopes, and success-probability correlations across these settings.

  • Hardness versus clause density: The time-to-solution peaks at clause density α ≈0.17, identifying the hardest regime for the chosen random loop characteristics.The study focuses mainly on medians because higher quantiles are noise-dominated with 100 instances per setting.
  • Hardness versus clause density: The frustration fraction peaks at α ≈0.25 and is correlated with problem hardness, although its maximum does not coincide exactly with the time-to-solution peak.Frustration is measured as the fraction of graph edges unsatisfied by the planted solution.
  • Speedup and correlations: A positive speedup-ratio slope indicates a possible DW2 advantage, observed for α > 0.4 against SAS, SQA, SSSV, and HFS.A negative slope instead indicates a definite DW2 slowdown.
  • Hardness versus clause density: All tested algorithms exhibit an easy-hard-easy pattern separated at α ≈0.2, but this transition is not identified with a spin-glass phase transition.The authors relate the pattern to prior SAT-like behavior without determining which phases occur in this problem set.
  • Speedup and correlations: At α = 0.35, success probabilities are strongly correlated between DW2 annealing times and between DW2 and SAA, with values progressing from high at small L to lower values at larger L.Similar correlations occur across annealing times for all α values and between DW2 and SAA at intermediate α values.

B. General considerations concerning scaling and speedup

The paper defines scaling-based speedup comparisons while emphasizing that annealing time must be optimized for each problem size. Because the DW2 has finite size and its tested minimum annealing time is suboptimal, the experiments can rule out speedup in some regimes but cannot confirm one.

  • Speedup definitions: The DW2 speedup ratio compares the device with algorithm X, and its slope with problem size—not its numerical value—determines scaling advantage or slowdown.A positive slope indicates a DW2 speedup, whereas a negative slope indicates a slowdown.
  • Speedup definitions: Annealing time must be optimized for each problem size because fixed-time speedup ratios are lower bounds on optimized speedup and can create a fake speedup.The optimal annealing time is denoted topt_a(L), while the experimental comparison uses a fixed ta.
  • Bounding speedup: For a physical DW2 with finite maximum problem size, the asymptotic speedup definition is not directly meaningful, so the analysis can identify a slowdown regime L− but not establish L+.The authors state that the best possible observation would extend L+ across the device’s available sizes, but their data cannot confirm it.
  • Bounding speedup: The tested DW2 minimum annealing time ta = 20µs is too long, making observed speedup-ratio slopes lower bounds on optimal scaling.Without identifying topt_a(L), the authors do not know how to infer or estimate L+; they use a monotonicity assumption to bound L−.
  • Bounding speedup: A slowdown observed with a suboptimal annealing time rules out a DW2 speedup under the stated comparison.This inference applies when ta > topt_a(L) in the relevant regime.

C. Scaling and speedup ratio results

Across clause densities, time-to-solution follows exponential-in-size scaling, while the DW2's relative performance depends strongly on problem hardness. The DW2 is worse than classical algorithms on harder, more frustrated instances, but a possible advantage remains at higher clause densities.

  • For L >∼4, all algorithms exhibit TTS(λ) ∼exp[b(α)L], with solver-dependent scaling coefficient b(α).
  • Figure 8 compares DW2 and SAA success-probability vectors across annealing times using normalized Euclidean distance, with uncertainty estimated by bootstrapping.
  • The DW2 has worse scaling than classical algorithms at lower clause densities, where problems are harder and more frustrated, so no speedup is possible.
  • A DW2 speedup remains possible at higher clause densities, where the device appears to find easier, less frustrated problems more readily than classical solvers.
  • For α ≥0.4, the apparent advantage is most pronounced and may extend even against the highly fine-tuned HFS algorithm.

D. Scaling coefficient results

The DW2 success-probability distributions are nearly insensitive to annealing times of at least 20 µs, and their scaling coefficients collapse across the tested times. Comparing coefficients leaves a possible high-clause-density speedup against HFS and SAS, but annealing-time optimization limits the conclusion.

  • Repeating DW2 experiments for ta ∈[20, 40]µs tests whether annealing time changes success probabilities.
  • Small Euclidean distances between DW2 success-probability vectors at ta = 20µs and ta = 40µs suggest that distributions have nearly reached their asymptotic values for ta ≥20µs.
  • The fitted DW2 scaling coefficients b(α) collapse across annealing times, indicating that b(α) has nearly reached its asymptotic value.
  • A DW2 speedup over algorithm X is impossible when bDW2(α) ≥bX(α), but remains possible when bDW2(α) < bX(α).
  • Figures 9 and 10 allow a possible speedup against HFS and SAS at sufficiently high clause densities.
  • The possible high-density speedup could disappear if annealing times shorter than 20µs were available for optimization.

E. DW2 vs SAA

The DW2 success probabilities appear compatible with thermal-annealer behavior for these problems, motivating comparison with simulated annealing. Its scaling coefficients are statistically indistinguishable from SAA's, but this does not rule out a DW2 speedup because SAA sweeps were not optimized.

  • Earlier studies ruled out SAA as a D-Wave model for random Ising problems and for Hamiltonians with opposite quantum-annealing and SAA predictions.
  • For the present problems, nearly asymptotic DW2 ground-state probabilities suggest that the device may perhaps be described as a thermal annealer.
  • DW2 and SAA scaling coefficients are statistically indistinguishable, but the comparison does not rule out a DW2 speedup because SAA's number of sweeps was not optimized.

V. DISCUSSION

The study finds no DW2 speedup for the hardest, low-clause-density instances, while higher-clause-density problems leave open a possible speedup. Control errors, decoherence, and insufficiently demanding benchmarks remain major barriers to a conclusive demonstration.

  • Speedup bounds: No DW2 speedup is observed at low clause densities corresponding to the hardest optimization problems, while higher densities leave a speedup possible.The authors report slightly improved performance at higher percentiles for the higher-clause-density regime.
  • Thermal behavior: The DW2 and SAA scaling coefficients closely match, suggesting asymptotic SAA models DW2 performance as temperature decreases.SAA performance improves steadily with increasing final inverse temperature at 50,000 sweeps.
  • Decoherence: The asymptotic DW2 ground-state probability agrees with a Gibbs distribution, consistent with weak system-bath coupling and energy-basis decoherence.This remains compatible with maintaining ground-state coherence, a condition identified as necessary for quantum-annealing speedup.
  • Experimental limitations: Control errors can make DW2 solve the wrong problem and substantially worsen classical annealing scaling when comparable noise is added.The authors suggest improved engineering and error correction could mitigate this disadvantage.
  • Future requirements: Conclusive quantum-speedup demonstrations require harder benchmark problems, reduced decoherence and control noise, and incorporated error correction.The authors also identify theoretical design of problems provably benefiting from quantum annealing as an outstanding challenge.
  • Benchmark design: The tunable-hardness frustrated-problem construction is proposed as a general benchmarking tool for quantum annealers.The authors suggest more finely tuned clause choices could eventually clarify quantum–classical performance differences.

Appendix A: Methods

The appendices describe the hardware, benchmark solvers, solution-enumeration procedure, and Bayesian success-probability analysis used in the experiments.

  • Hardware and instances: The experiments used 503 functional DW2 qubits within L × L Chimera subgraphs, generating 100 instances for each clause density and problem size.The full dataset contained 12,600 instances.
  • Classical solvers: HFS exploits Chimera sparsity by repeatedly optimizing over wide induced trees until further improvement is unlikely.The algorithm is tailored to the Chimera graph's local connectivity.
  • Classical solvers: The study compared DW2 with SA, SQA, SSSV, and HFS, including algorithms intended to model or directly compete with quantum annealing.SQA uses discrete-time path-integral quantum Monte Carlo rather than open-system quantum evolution.
  • Constraint solver: The planted-solution enumeration algorithm is exhaustive and guaranteed to find all solutions, but its bit-elimination order can exceed time and memory limits.Choosing the optimal elimination order is NP complete.
  • Statistical analysis: Success probabilities were estimated with a Bayesian beta posterior using the Jeffreys prior for repeated solver runs.The Jeffreys prior is selected for reparameterization invariance and information properties.
  • Statistical caveat: Correlations between successive runs could inflate empirical success probabilities for hard problems, although the authors argue this does not affect their conclusions.The observed potential advantage concerned easier, high-clause-density problems rather than the hardest instances.

Appendix B: Additional results

Additional results examine degeneracy, hardness, annealing-time selection, and percentile robustness, reinforcing a shared hardness peak across solvers.

  • Degeneracy and hardness: Ground-state degeneracy decreases rapidly with clause density and becomes unique up to global Z2 symmetry at sufficiently large α.The threshold depends on problem size.
  • Hardness peak: All solvers show a time-to-solution peak near α ≈0.2 across the tested Chimera sizes.The comparison uses the 25th and 75th TTS percentiles.
  • Annealing-time selection: The DW2 results show no lower envelope across annealing times, supporting the conclusion that ta = 20µs is suboptimal.Classical solver curves do form clear lower envelopes from which optimal sweep counts can be extracted.
  • Degeneracy and hardness: The Pearson correlation between HFS time-to-solution and degeneracy is −0.046, showing no observed trend at L = 8 and α = 0.4.The scatter plot covered 100 instances.
  • Scaling: The optimal SAA sweep count appears to scale exponentially with L at smaller clause densities, implying exponential TTS growth there.The conclusion follows because TTS is proportional to the optimal sweep count.
  • Robustness: Speedup-ratio results are qualitatively similar at the 25th and 75th success-probability percentiles, with a small improvement relative to HFS at the higher percentile.This tests sensitivity to the chosen percentile.

6. Additional scaling analysis plots

Further plots assess scaling fits, convergence, solver variants, and coupling-precision effects in the additional scaling analysis.

  • Scaling fits: Straight-line fits of run counts versus problem size are good, and their slopes and intercepts collapse consistently across annealing times.The slopes provide the b(α) values used in the scaling analysis.
  • Convergence: SAA's scaling coefficient converges within 2σ error bars as the sweep count increases from 5,000 to 50,000.This is shown as a convergence check for the asymptotic coefficient.
  • Solver variants: SAS has a smaller scaling coefficient than SQAS at large α, while small-α comparisons remain inconclusive because error bars overlap.The comparison concerns solver versions that retain the lowest energy found during the anneal.
  • Scope: The additional analysis does not explore whether continuous-time SQA would remove the reported discrete-time scaling advantage over SA.That possibility is noted but left untested.
  • Precision effects: The coupling scaling factor increases with clause density at fixed L and with L at fixed α, amplifying DW2 control-error and thermal effects.The authors report that this does not heavily impact the region where a speedup is possible.
Loading 1502.01663v3…