PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Annealing amid Local Ruggedness and Global Frustration

James King, Sheir Yarkoni, Jack Raymond, Isil Ozfidan, Andrew D. King, Mayssam Mohammadi Nevisi, Jeremy P. Hilton, Catherine C. McGeoch

arXiv:1701.04579v2quant-ph

TL;DR

The paper addresses the limited real-world relevance of synthetic inputs whose hardness relies heavily on tuned gadgets. It introduces problems with planted frustration in larger spin-glass backbones and evaluates them on a 2000-qubit D-Wave QPU, which outperforms software solvers in optimization and ground-state sampling.

  • Problem

    Existing Google problems emphasize tunneling but rely on easy spin-glass backbones, limiting their relevance to real-world problems.

    Source: A. Proposing a new problem class · p. 2

  • Method

    The paper proposes synthetic inputs deriving much of their computational hardness from larger spin-glass backbones with planted frustration and evaluates them on a 2000-qubit D-Wave QPU.

    Source: A. Proposing a new problem class · p. 2, §I · p. 2

  • Results

    The D-Wave QPU maintains roughly three orders of magnitude speed advantage across several sampling metrics and provides sample diversity as good as or better than software competition.

    Source: §VII · p. 12

  • Takeaways & Limitations

    The problem class provides an alternative to Google problems that is more representative of real-world problems while retaining a focus on quantum tunneling.

    Source: §VII · p. 12

Abstract

from arXiv · show

A recent Google study [Phys. Rev. X, 6:031015 (2016)] compared a D-Wave 2X quantum processing unit (QPU) to two classical Monte Carlo algorithms: simulated annealing (SA) and quantum Monte Carlo (QMC). The study showed the D-Wave 2X to be up to 100 million times faster than the classical algorithms. The Google inputs are designed to demonstrate the value of collective multiqubit tunneling, a resource available to D-Wave QPUs but not to simulated annealing. But the computational hardness in these inputs is highly localized in gadgets, with only a small amount of complexity coming from global interactions, meaning that the relevance to real-world problems is limited. In this study we provide a new synthetic problem class that addresses the limitations of the Google inputs while retaining their strengths. We use simple clusters instead of more complex gadgets and more emphasis is placed on creating computational hardness through frustrated global interactions like those seen in interesting real-world inputs. The logical problems used to generate these inputs can be solved in polynomial time [J. Phys. A, 15:10 (1982)]. However, for general heuristic algorithms that are unaware of the planted problem class, the frustration creates meaningful difficulty in a controlled environment ideal for study. We use these inputs to evaluate the new 2000-qubit D-Wave QPU. We include the HFS algorithm---the best performer in a broader analysis of Google inputs---and we include state-of-the-art GPU implementations of SA and QMC. The D-Wave QPU solidly outperforms the software solvers: when we consider pure annealing time (computation time), the D-Wave QPU reaches ground states up to 2600 times faster than the competition. In the task of zero-temperature Boltzmann sampling from challenging multimodal inputs, the D-Wave QPU holds a similar advantage as quantum sampling bias does not seem significant.

I. INTRODUCTION

The paper introduces synthetic problems that retain tunneling-relevant structure while deriving more hardness from planted frustration in larger spin-glass backbones. It evaluates these problems on the 2000-qubit D-Wave QPU, which finds ground states up to 2600 times faster than the software competition.

A. Proposing a new problem class

  • Earlier synthetic inputs either offered too little or too much potential benefit from quantum tunneling for ideal annealer evaluation.Google problems showed speedups up to 100 million times over SA and QMC, but their easy spin-glass backbones limit real-world relevance and allow some cluster-detecting algorithms to solve them readily.Source: A. Proposing a new problem class · p. 2
  • The new problem class shifts computational hardness from finely tuned gadgets toward larger spin-glass backbones with planted frustration.Its logical problems are planar Ising models without fields and solvable in polynomial time, while frustration creates difficulty for heuristics unaware of the planted class.Source: A. Proposing a new problem class · p. 2

B. Evaluation of the 2000-qubit D-Wave QPU

  • The evaluation measures QPU performance and its response to problem ruggedness using a stronger software competition that includes GPU implementations.The competition also includes Selby’s HFS implementation [9], the fastest software solver in a broader Google-problem analysis.Source: B. Evaluation of the 2000-qubit D-Wave… · pp. 2–3
  • Up to 2600 times faster, the D-Wave QPU found ground states than the software competition.The study also found a similar advantage for sampling from ground states without struggling to find diverse optimal solutions.Source: B. Evaluation of the 2000-qubit D-Wave… · p. 3

II. D-WAVE QUANTUM PROCESSING UNITS

D-Wave processors minimize Ising energy functions on a Chimera working graph. The paper describes the graph structure and the subgraph sizes used to vary problem scale.

A. Ising minimization

  • Ising minimization assigns ±1 values to spin variables to minimize energy given fields and couplings.Optimal solutions are ground states; the problem can be transformed to QUBO or MAX W2SAT forms, which are NP-hard.Source: A. Ising minimization · p. 3

B. Chimera topology

  • The native D-Wave topology is a C16 Chimera graph with 2048 vertices and 6016 edges.Each Chimera cell is a K4,4, and vertices connect within their cell and to neighboring cells.Source: B. Chimera topology · p. 3
  • Problem sizes range from C4 with 128 vertices to C16 with 2048 vertices, with variables increasing quadratically in Chimera size.Performance is measured against Chimera size because difficulty tends to scale exponentially with it, corresponding to the square root of the number of qubits.Source: B. Chimera topology · p. 3
  • The study’s working graph contains 2035 operational qubits out of 2048.The hardware working graph is a subgraph of C16 because fabrication and trapped magnetic flux leave some qubits unusable.Source: B. Chimera topology · p. 3

C. Quantum annealing

D-Wave quantum annealing transitions from an initial ground state toward a problem Hamiltonian whose ground state represents an optimal solution. The paper evaluates annealing time separately from total runtime, while noting that real devices require empirical performance analysis.

C. Quantum annealing

  • The problem Hamiltonian matches the Ising energy function, so its ground state is a minimum-cost solution.Quantum annealing gradually transitions from the initial ground state to the state described by the problem Hamiltonian.Source: C. Quantum annealing · p. 4
  • Real-device interference can reduce the probability of reaching a ground state, so ideal closed-system solution-time guarantees may not apply to D-Wave QPUs.The paper therefore treats QPUs as heuristic solvers requiring empirical performance analysis.Source: C. Quantum annealing · p. 4

D. Modeling performance

  • Sample time is annealing time plus readout time, while total time adds programming time and repeats across k samples.For this system, median programming time is 9.5 ms and median readout time is 123 µs.Source: D. Modeling performance · p. 4
  • The study typically reports annealing time rather than total time to measure algorithm performance and avoid obscuring trends with overhead.A 1000-times annealing-time speedup, typical for the QPU in this study, translates roughly to a 30-times total wall-clock speedup including programming and readout.Source: D. Modeling performance · p. 4

III. FRUSTRATED CLUSTER LOOP PROBLEMS

The paper builds frustrated cluster loop (FCL) problems by combining locally rugged clusters with globally frustrated logical problems. The simpler single-cell clusters retain tall, thin energy barriers while larger logical graphs provide global structure.

A. Ruggedness and clusters

  • Single-cell ferromagnetic clusters induce local ruggedness, replacing the earlier two-cluster gadgets with a simpler problem class.Flipping a cluster creates a barrier separating local minima.Source: A. Ruggedness and clusters · p. 5

B. FCL problem generation

  • FCL problems join ferromagnetic Chimera unit-cell clusters using frustrated loop problems on a square logical lattice.The logical lattice spans 16×16 clusters on the 2000-qubit QPU.Source: B. FCL problem generation · p. 5
  • The cluster wells create tall, thin barriers while the logical problem supplies global frustration and a macroscopically interesting energy landscape.The logical graph is formed from logical spins and couplers corresponding to complete unit cells and the connections between them.Source: B. FCL problem generation · p. 5
  • Logical problems use α and ρ as in King et al. [36] and map to zero-field native Chimera couplings: in-tile values are −1, inter-tile values are JL/R, and all lie in [−1, 1] when ρ≤R and ρ≥|j| for each logical coupling j.Source: B. FCL problem generation · p. 6
  • The repetition code inherent in logical couplers and spins makes these full-working-graph problems relatively robust to analog errors.Disconnected logical inputs are rejected during generation.Source: B. FCL problem generation · p. 6

C. Problem class parameters

FCL difficulty is tuned with α, ρ, and R: α sets logical hardness, while ρ and R shape the distribution and relative strength of local ruggedness.

C. Problem class parameters

  • Low α leaves problems underconstrained, whereas high α strengthens the planted solution and makes the problem more ferromagnet-like and easier.Logical difficulty depends on α and ρ, not R.Source: C. Problem class parameters · p. 6
  • The hardest α depends on ρ: difficulty peaks at α = 0.65, 0.75, 0.8, and 0.85 for ρ values 3, 4, 5, and 6, respectively.Difficulty is measured by expected samples to solution for simulated annealing.Source: Figure 1 · p. 6, C. Problem class parameters · p. 6
  • For fixed α, lower ρ spreads loops more evenly; higher ρ constrains R to be higher and makes local ruggedness stronger relative to the global Hamiltonian.The native inter-tile couplings are scaled by R ≥ ρ.Source: C. Problem class parameters · p. 6
  • Setting R = ρ simplifies generation, while varying R at fixed ρ isolates ruggedness without changing logical complexity.Varying R also makes ruggedness tunable for assessing quantum tunneling and quantum annealing.Source: C. Problem class parameters · p. 6

D. Confirming correlation between ruggedness and classical hardness

The study finds that greater ruggedness accompanies greater classical hardness, then evaluates the problems against GPU-based software solvers and HFS.

D. Confirming correlation between ruggedness and classical hardness

IV. SOFTWARE SOLVERS

  • The software comparison includes GPU implementations of SA, QMC, and SVMC, plus Selby’s CPU implementation of HFS.Modern GPU implementations are roughly 1000 times faster than corresponding single-core CPU implementations.Source: §IV · p. 7
  • GPU solvers raise the software-comparison bar because SA is highly amenable to GPU implementation, whereas many algorithms in a broader solver set lack GPU parallelizability and low memory requirements.The cited analysis identifies sequential algorithms as the only class with those properties, despite their worst performance in that study.Source: §IV · p. 7

V. OPTIMIZATION

The optimization experiments compare D-Wave and software solvers on FCL inputs using annealing time. With R = ρ, D-Wave reaches solutions faster, with a peak reported speedup of 2600 times.

V. OPTIMIZATION

  • Time to solution is calculated from time per anneal and ground-state probability, excluding programming and readout times.Annealing lengths for non-HFS solvers are optimized for the largest input size, making them too long on smaller inputs.Source: §V · p. 7, A. Varying ruggedness via logical… · p. 8

A. Varying ruggedness via logical complexity

  • The first experiment varies ρ while setting R = ρ, so the same parameter controls both ruggedness and logical complexity.For each ρ, α is chosen to maximize logical hardness; 100 problems per size and parameter selection are evaluated with each solver.Source: A. Varying ruggedness via logical… · p. 7, §V · p. 7
  • As ρ rises with R = ρ, simulated annealing degrades sharply, while D-Wave and QMC decline more gradually and HFS decreases only slightly.HFS updates include whole clusters and are tailored to the Chimera topology; its slight degradation is attributed to increased logical hardness.Source: A. Varying ruggedness via logical… · pp. 7–8
  • At the largest size, D-Wave is three orders of magnitude faster than the fastest software solver for every ρ; its speedup peaks at 2600 times for ρ = 4.The figure reports median time to solution over 100 inputs at each size, with 95% confidence intervals.Source: A. Varying ruggedness via logical… · p. 7, Figure 3 · p. 8
  • True scaling is masked by the inability to optimize parameters for smaller inputs, although D-Wave scales at least as well as software between the two largest sizes.This qualification limits interpretation of the reported scaling curves.Source: A. Varying ruggedness via logical… · p. 8

B. Varying ruggedness by scaling

Increasing ruggedness while holding logical complexity constant makes simulated annealing struggle most, while the D-Wave QPU is most capable of handling it. The section also defines a ground-state valley-sampling metric and a tractable procedure for selecting inputs with multiple, well-separated valleys.

B. Varying ruggedness by scaling

  • The D-Wave QPU handles increasing ruggedness best, followed by QMC, SVMC, and SA; HFS performance is constant in this example.The experiment fixes ρ = 3 and varies R on the largest problem size, a 16 × 16 logical lattice, to isolate ruggedness.Source: B. Varying ruggedness by scaling · p. 8, Figure 4 · p. 8

VI. SAMPLING

  • Zero-temperature sampling simplifies the study by avoiding an inverse-temperature parameter that would need arbitrary or empirical selection.The authors note that estimating β can be challenging and that deriving it from a solver's output could give that solver an unfair advantage.Source: §VI · p. 9

A. Sampling from all valleys

  • A valley is a set of ground states connected in logical Hamming space; antipodal valley pairs are treated as one because transitions between them are trivial.Ground states can be adjacent in logical space despite being separated by a single tall, thin energy barrier; modest postprocessing can traverse a valley.Source: A. Sampling from all valleys · p. 9
  • Time-to-all-valleys (TTAV) measures expected annealing time to sample every ground-state valley, capturing the challenge of finding ground states in every mode.With a sample from each valley, all ground states can be found with modest postprocessing; TTAV is interpreted relative to TTS.Source: A. Sampling from all valleys · p. 9

B. Mining for interesting valley structure

  • Inputs with multiple, well-separated ground-state valleys are sought because sampling them is particularly hard and has applications such as deep Boltzmann-machine classification.Lower mean absolute spin overlap tends to indicate more widely separated valleys.Source: B. Mining for interesting valley… · pp. 9–10
  • The mining procedure rejects inputs with over 1000 ground states, fewer than four valleys, or mean overlap of 0.7 or higher.The authors use logical-space valley structure to make analysis tractable; the largest logical graphs are 16 × 16 lattices with treewidth 16.Source: B. Mining for interesting valley… · pp. 9–10

C. Sampling results

On selected inputs with multiple, separated valleys, the D-Wave QPU reaches all valleys substantially faster than the fastest software solver. Its valley-distribution KL-divergence is also superior, even with much less annealing time, and the results do not show significant sampling bias for these problems.

1. Time to all valleys

  • 30 ms: the D-Wave QPU's median time to hit all valleys, versus roughly 30 s for HFS, the fastest software solver.The study generated 50,000 inputs and retained 74 after mining for interesting valley structure.Source: §1 · p. 10, C. Sampling results · p. 10
  • About three orders of magnitude: the D-Wave QPU outperforms the competition on TTAV despite a slightly less-steep curve than HFS.The curve slope may indicate less diverse D-Wave samples, but sampling bias does not appear to be a significant problem here.Source: §1 · p. 10

2. KL-divergence of valley distributions

  • The KL-divergence comparison measures empirical valley distributions against exact relative valley sizes and is infinite if a solver misses any valley.The measure includes both distributional error and finite-sample estimation error, with samples conditioned on being ground states.Source: §2 · p. 10
  • The D-Wave QPU has a superior KL-divergence distribution to every software solver while annealing for three orders of magnitude less time.For the single input where its KL-divergence was infinite because a valley was never seen, all other solvers also had infinite KL-divergence.Source: §2 · p. 10

3. Raw error on model marginals

The raw marginal analysis finds that the D-Wave QPU reaches low logical-space spin-spin marginal error much faster than software solvers. The conclusions report a broader speed advantage across optimization and sampling, with tunable ruggedness and no strong sampling-bias concern in the tested inputs.

3. Raw error on model marginals

  • At 0.5 s, the D-Wave QPU’s median L1 error is below 1%, a level software solvers fail to reach in 100 s; it is roughly 1,000× faster.The analysis measures couplers in logical space, ignoring couplers within a cluster.Source: §3 · pp. 10, 12, Figure 7 · p. 12

VII. CONCLUSIONS

  • The synthetic inputs are presented as more real-world-representative than Google problems because their hardness relies less on tuned gadgets and more on planted frustration in larger spin-glass backbones.The paper describes them as an alternative to Google problems of Denchev et al..Source: §VII · p. 12
  • Up to 2,600× faster than the software solvers considered, the D-Wave QPU typically achieves roughly 1,000× speedup at the largest problem size.The comparison includes GPU implementations of SA, QMC, and SVMC, plus a CPU implementation of HFS; the set is representative but not exhaustive.Source: §VII · p. 12
  • The inputs’ tunable ruggedness is controlled by ρ or S; as ruggedness increases, QMC improves relative to SA and physical quantum annealing performs better still.Source: §VII · p. 12
  • For zero-temperature Boltzmann sampling, the D-Wave QPU retains a roughly 1,000× speed advantage and provides sample diversity as good as or better than software solvers, with little evidence of sampling-bias difficulty.Source: §VII · p. 12

Appendix A: Calculation of decorrelation

The appendix estimates decorrelation time through parallel tempering and integrated autocorrelation of the temperature index. The included software baselines span GPU-oriented Monte Carlo methods and a topology-tailored HFS implementation.

Appendix A: Calculation of decorrelation

  • The temperature random walk’s integrated autocorrelation approximates decorrelation time; the procedure uses increasing inverse temperatures, random initialization, and 600,000 sweeps with an initial 10% discarded as burn-in.Temperatures span β ∈ [0, 30], with exchange rates heuristically equalized near 40%; autocorrelations are averaged across chains using an initial sequence estimator.Source: Appendix A · pp. 14–15

1. Classical hardware

  • Classical processor specifications are reported for the software solvers; CPU jobs run single-threaded while each GPU job uses the whole GPU.Source: §1 · p. 15

2. Included software solvers

  • The evaluation includes GPU implementations of SA, QMC, and SVMC, alongside Selby’s CPU implementation of HFS.Source: §2 · p. 15

a. Simulated annealing

  • SA simulates thermal annealing and is suited to GPU implementation because it is simple, memory-light, and highly parallelizable.Source: a. Simulated annealing · p. 15

b. Quantum Monte Carlo

  • QMC is a classical approximation to quantum annealing; the GPU implementation uses discrete time and 64 Trotter slices, while continuous-time QMC is more faithful but discrete-time QMC can optimize better.Source: b. Quantum Monte Carlo · p. 15

c. Spin vector Monte Carlo

d. Hamze-de Freitas-Selby

  • HFS greedily optimizes spins in changing low-treewidth induced subgraphs with the rest fixed; its Chimera-tailored implementation cannot be efficiently run on GPUs because of memory demands.The authors modified Selby’s implementation [9] to return each stopping state for consistency with other heuristic solvers.Source: d. Hamze-de Freitas-Selby · p. 15

3. Excluded software solvers

The authors excluded or constrained several software solvers because of performance, resource, or topology considerations. Parameter tuning focused on the largest problem size, so scaling results are qualified accordingly.

3. Excluded software solvers

  • Several additional software solvers were excluded because they were prohibitively slow and available time and resources did not permit the long runs needed for parameter optimization.Source: §3 · p. 15

a. Nontailored HFS

  • Topology-agnostic HFS performed far worse than Selby’s tailored implementation and missed ground states on the largest problems; the tailored subgraphs exploit Chimera’s sparsity and modularity.The authors state that this exploitation is likely impossible on future quantum-annealer topologies.Source: a. Nontailored HFS · pp. 15–16

b. Wolff cluster Monte Carlo

  • The CPU Wolff cluster implementation was uncompetitive because cluster detection was slow, despite clusters seeming well suited to FCL problems.GPU Wolff implementations on lattice topologies achieve only modest speedups over CPU implementations.Source: b. Wolff cluster Monte Carlo · p. 16

c. Parallel tempering

  • Parallel tempering was more powerful than SA but uncompetitive here because each step cost more.The implementation used 64 replicas.Source: c. Parallel tempering · p. 16

d. PT-ICM

  • PT-ICM scaled similarly to Selby’s HFS but was an order of magnitude slower even with input-specific ideal temperature ladders; its cluster-update advantage may erode on denser topologies.Its effectiveness depends on a large site-percolation threshold, which decreases as processor density increases.Source: d. PT-ICM · p. 16

4. Parameter tuning

  • Because the D-Wave QPU performed best at the minimum 5 µs anneal, software parameters were optimized at the largest size, and scaling results should be treated cautiously.SA, QMC, and SVMC schedules and sweep counts were selected to optimize performance; HFS used Selby’s GS-TW2 strategy.Source: §4 · pp. 16–17
Loading 1701.04579v2…