PaperlayerView exact revision on arXiv

Source-linked AI summary

The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)

Salvatore Mandrà, Helmut G. Katzgraber, Creighton Thomas

arXiv:1703.00622v2quant-phcond-mat.dis-nn

TL;DR

Planar, carefully crafted quantum-annealing benchmarks can have logical structure that makes them tractable for efficient classical optimization. This paper analyzes such benchmarks and shows that exact polynomial-time methods can solve them; it also proposes alternative benchmark directions.

  • Problem

    Quantum-annealing speedup remains elusive, and crafted planar benchmarks may be too structurally simple to establish an advantage over classical optimization.

    Source: §I · p. 1

  • Method

    The paper analyzes planar crafted benchmarks using classical optimization methods, including minimum-weight perfect matching for unbiased planar spin-glass problems.

    Source: A. Minimum-weight perfect matching… · p. 2, §I · p. 2

  • Results

    MWPM solves planar unbiased spin-glass problems exactly in polynomial time, while the D-Wave 2000Q and ICM scale exponentially and MWPM polynomially on the reported benchmarks.

    Source: A. Minimum-weight perfect matching… · p. 2, §IV · p. 4

  • Takeaways & Limitations

    The authors recommend nonplanar logical benchmark topologies and identify anticlusters and physical simulation of quantum Hamiltonians as possible alternatives.

    Source: §V · p. 4

    The stated exact polynomial-time MWPM result applies to planar two-dimensional spin-glass problems without biases.

    Source: A. Minimum-weight perfect matching… · p. 2

Abstract

from arXiv · show

In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully-crafted gadget-based problems whose logical structure has typically a planar topology. Recent experiments on these gadget problems using a commercially-available quantum annealer have demonstrated an impressive performance over a selection of commonly-used classical optimization heuristics. Here we show that efficient classical optimization techniques, such as minimum-weight perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly-used benchmark problems based on planar logical topologies.

I. INTRODUCTION

The search for quantum speedup in analog quantum annealing remains unresolved, while crafted planar benchmarks may have structure that efficient classical algorithms can exploit. This work argues that planar benchmarks should be compared with exact polynomial-time methods and discusses ways to avoid that limitation.

I. INTRODUCTION

  • The D-Wave 2000Q minimizes quadratic unconstrained binary cost functions by quenching transverse-field-induced quantum fluctuations.Its variables are Boolean spins, with couplings and biases defining the cost function.Source: §I · p. 1
  • Benchmark problems should use the chip’s complete variable set without becoming trivial, despite embedding overhead that reduces the number of logical sites.The introduction notes that real-world problems embedded on the Chimera topology typically use multiple physical variables per logical variable.Source: §I · p. 1
  • Planar logical benchmarks can be solved by exact polynomial-time methods, so annealers would need to scale polynomially to compete with state-of-the-art classical algorithms for frustrated planar problems.The authors identify MWPM as such an algorithm and say both Denchev et al.’s and King et al.’s benchmark instances can be solved in polynomial time.Source: §I · p. 1
  • Earlier benchmark designs sought to frustrate common heuristics, but later work found that stronger classical optimization could outperform the annealer and simulated quantum annealing.The authors cite results showing time-to-solution scaling considerably better for state-of-the-art optimization than for the D-Wave device on Denchev et al.’s benchmarks.Source: §I · p. 1
  • If claims of large speedups rely on fast heuristics as baselines, studies should also include state-of-the-art algorithms for planar topologies.The authors distinguish methods such as Hamze–de Freitas–Selby and parallel tempering from the true state of the art for planar problems.Source: §I · p. 2
  • The paper’s remaining sections describe crafted problems, classical methods, results, and strategies for designing planar-device problems that resist polynomial algorithms.The proposed strategies are framed around problems that cannot be solved with polynomial algorithms for planar technologies.Source: §I · p. 2

II. D-WAVE’S CRAFTED PROBLEMS

The crafted frustrated cluster loop benchmarks are defined on a two-dimensional logical lattice rather than directly on the full Chimera topology. Their construction creates rugged energy landscapes while making the logical topology—not the physical embedding—the appropriate basis for comparison.

II. D-WAVE’S CRAFTED PROBLEMS

  • The D-Wave 2000Q’s Chimera hardware consists of coupled K4,4 unit cells, and arbitrary logical topologies can be embedded by using multiple physical variables per logical variable.Only native Chimera couplings can be independently tuned, within [−1, +1].Source: §II · p. 2
  • FCL problems appeal as benchmarks because many classical heuristics struggle to minimize their cost function, although their optimal configuration can be deduced from the problem structure.The cited benchmark instances are carefully crafted for the D-Wave 2000Q.Source: §II · p. 2
  • Ferromagnetic couplings within each K4,4 cell force its physical qubits to act as one logical qubit, producing a two-dimensional lattice.The couplings inside each unit cell are set to Jij = −1.Source: §II · p. 2
  • FCL instances are generated on that logical topology with varying ruggedness, clause-to-variable ratio α, and precision ρ; disconnected graphs are discarded.The local ruggedness R is expected to satisfy R ≥ ρ, with logical interactions in [−R, +R].Source: §II · p. 2
  • FCL benchmarks use a two-dimensional logical lattice with open boundaries, so comparisons should use heuristics optimized for that logical problem rather than the Chimera topology.The D-Wave chip can solve problems on the full Chimera lattice, but the cited benchmarks are defined on the logical lattice.Source: §II · p. 2

III. METHODS

The methods section introduces the algorithms used and the benchmark’s time-to-solution definition, while directing readers to the cited reference for details of the ICM heuristic.

III. METHODS

  • The section outlines the algorithms used and defines the benchmark’s time-to-solution measure.The passage provides no further definition or formula.Source: §III · p. 2
  • Details of the isoenergetic cluster move heuristic are provided in reference.Source: §III · p. 2

A. Minimum-weight perfect matching algorithm

MWPM is an exact polynomial-time method for planar two-dimensional spin-glass optimization without biases. It maps the spin-glass problem to a matching problem, solves it exactly, and translates the solution back.

A. Minimum-weight perfect matching algorithm

B. Definition of time-to-solution

Time-to-solution (TTS) translates a heuristic’s success probability into an estimated runtime to obtain an optimum. The section contrasts a simple repeat-count estimate with a more accurate definition targeting 99% success.

B. Definition of time-to-solution

  • Figure 1 compares TTS scaling for the D-Wave 2000Q, ICM, and MWPM; MWPM outperforms the quantum device by several orders of magnitude on larger lattices.The plotted points are median TTS values, with error bars spanning the 5th–95th percentiles.Source: Figure 1 · p. 3
  • A simple TTS estimate multiplies runtime per attempt by an approximate 1/p repetitions to observe an optimum.The passage characterizes this estimate as naive.Source: B. Definition of time-to-solution · p. 4
  • The more accurate TTS definition estimates the repetitions needed for at least 99% success, accounting for uncertainty in heuristic results.It derives the required repetition count from the probability that all attempts fail.Source: B. Definition of time-to-solution · p. 4
  • At fixed success probability and per-attempt runtime, TTS2 is lower than TTS1; the authors prefer TTS2 because it gives a lower bound to overall probability.The paper converts the D-Wave data in Ref. from TTS1 to TTS2.Source: B. Definition of time-to-solution · p. 4

IV. RESULTS

The results compare the D-Wave 2000Q with ICM and MWPM. MWPM scales polynomially, while the D-Wave device and ICM scale exponentially; at larger sizes, MWPM becomes substantially faster.

IV. RESULTS

  • Doubling the D-Wave 2000Q’s largest logical problem size lets MWPM outperform it by approximately three orders of magnitude.The comparison uses artificial perfect Chimera problems up to 256 × 256 logical variables.Source: §IV · p. 4
  • MWPM scales polynomially with input size, whereas both the D-Wave 2000Q and ICM scale exponentially.The paper extends the comparison using artificial perfect Chimera lattices up to 256 × 256 logical variables.Source: §IV · p. 4
  • The D-Wave 2000Q is remarkably fast for small systems, but MWPM becomes faster as the logical problem size grows.The authors caution that CMOS systems run an operating system, kernel, and other concurrent processes, unlike the special-purpose annealer.Source: §IV · p. 4

V. DISCUSSION

The discussion argues that planar logical benchmarks are unlikely to establish quantum speedup against exact polynomial algorithms. It proposes nonplanar anticlusters and physical simulation of quantum Hamiltonians as alternatives.

V. DISCUSSION

  • Planar logical benchmarks are unlikely to reach quantum speedup unless the annealer performs exponentially faster than the exact polynomial algorithm.Source: §V · p. 4
  • Anticlusters contract links between K4,4 cells into logical variables, producing a nonplanar topology with high connectivity for benchmark construction.For a Chimera lattice with c × c K4,4 cells, the resulting lattice has 4c(c + 1) logical qubits; overlaying it with frustrated cluster loops or post-selected spin-glass problems is proposed as a way to generate hard benchmarks.Source: §V · p. 4
  • Using the D-Wave 2000Q to simulate nontrivial quantum-physics Hamiltonians is proposed as another route to demonstrate its capabilities.The authors say these Hamiltonians are hard to simulate classically even for small numbers of variables and that the device might outperform classical simulation techniques in the near future.Source: §V · p. 4

Related papers

Loading 1703.00622v2…