PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking a quantum annealing processor with the time-to-target metric

James King, Sheir Yarkoni, Mayssam M. Nevisi, Jeremy P. Hilton, Catherine C. McGeoch

arXiv:1508.05087v1quant-ph

TL;DR

Ground-state benchmarks can be computationally prohibitive and sensitive to analog noise. The paper introduces time-to-target, asking software solvers to match a D-Wave processor’s short-time solutions; D-Wave 2X was faster than competing software on most tested classes, but the study does not claim quantum speedup.

  • Problem

    Ground-state evaluation can become intractable on large inputs, while analog noise perturbs the processor’s input Hamiltonian.

    Source: §1 · p. 3

  • Method

    Time-to-target sets an energy target from the D-Wave processor’s distribution and measures how long competing solvers take to reach matching or better-quality solutions.

    Source: §1 · p. 3, §3 · p. 7

  • Results

    At full 1097-qubit scale, single-threaded software solvers generally had not kept up with D-Wave 2X, except on RAN1; pure-computation TTT times were 8x to 600x faster across tested classes.

    Source: §1 · p. 3, §6 · p. 16

  • Takeaways & Limitations

    The authors identify multithreaded, multi-core software solvers as the next comparison frontier.

    Source: §6 · p. 16

    The reported scaling curves should not be extrapolated to larger problem sizes or other quantiles because their shapes depend on how the target quantiles cut the solution-energy distributions.

    Source: §5 · p. 13

Abstract

from arXiv · show

In the evaluation of quantum annealers, metrics based on ground state success rates have two major drawbacks. First, evaluation requires computation time for both quantum and classical processors that grows exponentially with problem size. This makes evaluation itself computationally prohibitive. Second, results are heavily dependent on the effects of analog noise on the quantum processors, which is an engineering issue that complicates the study of the underlying quantum annealing algorithm. We introduce a novel "time-to-target" metric which avoids these two issues by challenging software solvers to match the results obtained by a quantum annealer in a short amount of time. We evaluate D-Wave's latest quantum annealer, the D-Wave 2X system, on an array of problem classes and find that it performs well on several input classes relative to state of the art software solvers running single-threaded on a CPU.

1 Introduction

The paper introduces time-to-target (TTT), which has solvers race to reach an energy target from the D-Wave processor and reduces evaluation’s runtime and analog-noise challenges. It reports faster D-Wave 2X TTT times than competing software on most tested classes, while limiting its comparison to tested problem sizes.

1 Introduction

  • Ground-state metrics are computationally prohibitive on large inputs, and analog noise can perturb the Hamiltonian so nominal ground states may exchange roles with excited states.Ground-state and excited-state roles may switch in the physical Hamiltonian, while near-ground states generally outnumber ground states.Source: §1 · pp. 2–3
  • Planted solutions and lower-bound proxies can help evaluate difficult instances, but representativeness is hard to establish and no suitable lower bound appears available for D-Wave’s native problems.The cited PTAS is described as mostly theoretical and impractical for getting within 10%.Source: §1 · pp. 2–3
  • TTT sets a target from the D-Wave processor’s energy distribution, then measures how long competing solvers take to find matching or better-quality solutions.The study used target solutions found within 15ms to 352ms.Source: §1 · p. 3
  • For total computation time, D-Wave 2X TTT was 2x to 15x faster than the best competing software at the largest problem sizes, except for one input class.A solver specific to that class was faster.Source: §1 · p. 3
  • For pure computation time, D-Wave 2X TTT was 8x to 600x faster than competing software across all tested input classes.This comparison omits I/O costs.Source: §1 · p. 3
  • The study compares runtime only within tested problem sizes and does not address quantum speedup.Source: §1 · p. 3

2 Overview

The overview describes D-Wave quantum annealing as a transition from an initial state to a problem Hamiltonian, while framing the processor as a heuristic whose performance must be measured empirically. It introduces the timing and problem-structure considerations used in the evaluation.

Overview

  • Problems are tested on square Chimera subgraphs from C4 to C12, with difficulty expected to scale exponentially in Chimera size.The number of variables grows as n = 8s^2, while treewidth grows linearly in s.Source: §2 · p. 4
  • D-Wave processors use quantum annealing to transition from an initial state to a problem Hamiltonian whose ground state corresponds to a minimum-cost solution.Theoretical guarantees assume an ideal closed system, whereas real-device interference can reduce the probability of reaching a ground state.Source: §2 · pp. 4–5
  • The timing model separates programming, annealing, and readout, and defines total time as T = ti + R ts.The overview also distinguishes computation time from the trade-off between time and solution quality.Source: §2 · p. 5
  • Increasing sample size R can improve the probability of observing low-cost solutions, while longer annealing above 20μs had little apparent effect on the tested classes.The study fixes anneal time at 20μs and focuses on the sample count needed to reach a target quality.Source: §2 · p. 5

3 The time-to-target (TTT) metric

The time-to-target metric compares how long solvers take to reach an energy target drawn from D-Wave 2X samples. It uses expected samples-to-target and can measure either total runtime or annealing time alone.

The time-to-target metric

  • Expected STT can be lower than 1/q because repeated samples may share quantized energy levels.For the example, STT values at q = 0.001, 0.01, and 0.1 are 413.2, 25.58, and 7.029, below bounds of 1000, 100, and 10.Source: §3 · pp. 6–7
  • TTT measures expected time for a solver to reach an energy target, combining samples-to-target with computation time.The target is selected from the reference processor’s sample-energy distribution for a specific input and quantile q.Source: §3 · pp. 6–7
  • TTTtotal includes programming and sample times for a user-facing wall-clock comparison, whereas TTTanneal includes only annealing time to examine algorithm scaling.The paper notes that I/O dominates computation costs in current processor models.Source: §3 · p. 7
  • For q = 0.001, 0.01, and 0.1, D-Wave 2X reaches the corresponding targets within at most 352ms, 46ms, and 15ms total computation time.These quantiles correspond to upper bounds of 1000, 100, and 10 hardware samples.Source: §3 · p. 7
  • Software solvers are compared by the time needed to match or beat D-Wave 2X target energies obtained within 15ms to 352ms.Software STT is estimated from samples, while hardware gauge transformations can add programming time.Source: §3 · p. 7

4 Experimental setup

The experimental setup evaluates D-Wave 2X and software solvers on Chimera-structured Ising problems using several problem classes and target-energy quantiles. Solver tuning and scope differ, and the reported metrics use samples from hardware and software.

4.1 Problems

  • For each problem class tested, the study generated 100 inputs per problem size across sizes from C4 (128 qubits) up to C12 (1097 qubits).The cited classes include RAN1, RAN3, RAN7, RAN127, AC3, AC3-odd, and FL3.Source: §4.1 · p. 8

4.2 Solvers

  • The comparison uses D-Wave 2X, simulated annealing, and HFS; software times use the fastest tuned version available for each input.HFS uses the treewidth-4 mode, which had better TTT performance than the tested treewidth-8 mode in every case.Source: §4.2 · pp. 8, 10

4.3 Metrics

  • Each solver’s outputs receive greedy descent post-processing, and HFS sampling mode returns local minima as independent samples.The study estimates software STT from 1,000 samples per input and hardware targets from 50,000 samples across 50 random gauge transformations.Source: §4.2 · pp. 8, 10, §4.3 · p. 10

4.2 Solvers

  • Software tuning and post hoc selection create an optimistic usage scenario, while default D-Wave settings make the comparison a lower bound on the user-observed performance gap.A solver restricted to RAN1 is included for that class despite not meeting the stated matched-scope criterion.Source: §4.2 · p. 9

5 Results

Selected results show large D-Wave 2X time-to-target advantages on several problem classes, alongside important differences by metric, target quantile, and solver. The section also cautions that observed scaling depends on target choice and tested conditions.

5 Results

  • For RAN1 problems, at C12 sizes, TTTanneal is between 8x and about 80x faster than the best competing software solvers we know of.Source: Figure 4 · p. 11, §5 · p. 13
  • For RAN1 at the largest sizes, DW2X is faster than HFS in total computation time, while the specialized SA solver is fastest across all three quantiles.The SA solver exploits bit parallelism and applies narrowly to the tested 1-bit problems.Source: Figure 5 · p. 12, §5 · p. 13
  • For RAN1, DW2X's constant 11.6ms programming time dominates TTTtotal in most cases, with computation rising above that threshold only at the largest, hardest-quantile problems.The threshold is exceeded only at the largest problems for q = 0.001.Source: Figure 5 · p. 12, §5 · p. 13
  • For RAN1, SA10000 is optimal in STT, but its long per-sample time means it is not necessarily best in TTTanneal.DW2X's 20μs per-anneal time makes its TTTanneal scaling identical to its STT scaling.Source: §5 · p. 12
  • From C4 to C12, problem size grows about 8-fold while TTT grows about 1000x, 1000x, and 100x across the three panels.The corresponding STT increases are about 10x, 10x, and 2x; for SA, time per sweep also grows quadratically with Chimera size.Source: §5 · p. 13
  • The observed scaling curves should not be extrapolated to larger sizes or other quantiles because their shapes depend on how the chosen quantiles cut the solution-energy distributions.For high-precision random instances, SA's relative performance degrades as precision increases; different parameterization could improve it.Source: §5 · pp. 13, 16
  • At the largest FL3 sizes, DW2X is about 600x faster than any competitor in TTTanneal for all measured quantiles.DW2X programming time dominates TTTtotal in nearly all FL3 cases.Source: §5 · p. 13, Figure 6 · p. 14
  • DW2X's relative performance generally peaks at q = 0.1 for TTTanneal and q = 0.01 for TTTtotal.For TTTtotal, lower relative performance at q = 0.001 is partly attributed to potentially needing multiple gauge transformations.Source: §5 · p. 16

6 Discussion

At the full 1097-qubit scale, single-threaded software solvers generally did not keep pace with DW2X in the TTT metrics, except on RAN1. The discussion points toward multithreaded, multi-core solvers as the next comparison, while noting that the required CPU resources remain unclear.

6 Discussion

  • Single-threaded software solvers did not keep pace with DW2X at the full 1097-qubit scale in these TTT metrics, except on RAN1.The authors say the comparison now turns to multithreaded, multi-core software solvers.Source: §6 · p. 16
  • The number of CPU cores needed to match DW2X in TTT metrics remains unclear; up to 16 threads were insufficient for anneal-time-only performance in many cases, even with idealized perfect parallelism.The authors call for actual timing on multi-CPU platforms, where memory access and communication costs may matter substantially.Source: §6 · p. 16
  • The study used only CPU-based software solvers; the authors are investigating GPU-based algorithms to estimate how many GPU cores would match DW2X in TTT metrics.Source: §6 · p. 16

A DW2X hardware working graph

  • The DW2X working graph is a 12 × 12 grid of Chimera tiles with 1097 of 1152 qubits active.The paper attributes inactive qubits to fabrication imperfections.Source: Figure 10 · p. 20

Software timing

  • Software timing used single-threaded Intel Xeon E5-2670 runs; SA and HFS initialization was timed 10 times using the minimum, while sweep time was measured over hundreds of thousands of sweeps using the mean.Sweep time grows linearly with spin count and quadratically with Chimera size; HFS uses an internally determined number of tree sweeps per sample.Source: Software timing · p. 21
  • For the an ms r1 nf solver, samples were requested in batches of 64, and batch success probability and annealing time were defined for those batches.A spin flip updates one variable in an inner-loop iteration; a sweep iterates through all n variables.Source: Software timing · p. 21

C Tuning SA

The SA implementation was tuned over sweep counts and two cooling schedules, with results reported using the best schedule and sweep count for each problem class.

C Tuning SA

  • To optimize SA’s sweep-count parameter, the study tested 10, 20, 40, 100, 200, 400, 1,000, 2,000, 4,000, and 10,000 sweeps per anneal for all inputs.The unscaled schedule raises β linearly from 0.01 to 3; it was too fast for high-precision RAN127 and RAN7, so the scaled schedule from 0.01/r to 3/r was used instead. Reported results for each problem class use the better schedule and sweep count.Source: C Tuning SA · pp. 21, 23
  • The unscaled schedule raised inverse temperature β linearly from 0.01 to 3, while the scaled schedule used 0.01/r to 3/r, with r the largest absolute Hamiltonian component.Source: C Tuning SA · p. 23

D Full results

The appendix presents full TTT and STT results across problem sizes, with median solver times and 95% confidence intervals. The reported software-solver comparison varies by problem class and input size.

D Full results

  • The appendix plots STT, TTTanneal, and TTTtotal by problem size, showing medians and 95% confidence intervals for each solver.STT plots use SA fixed at 10,000 sweeps; this is best for STT, but is best for TTT metrics only at the largest problem sizes.Source: D Full results · p. 23
  • For RAN1, an ms r1 nf is always the fastest SA implementation; for other inputs, estimated an ss ge fi times are lower by a constant factor than in-house SA except on small inputs.On small inputs, in-house SA is faster because of its lower initialization cost.Source: D Full results · p. 23

D.1 AC3-odd

  • The AC3-odd plots label problem sizes from C4 through C12 and identify solver series including DW2X, HFS, in-house SA, and an_ss_ge_.Source: §D.1 · p. 24

D.2 FL3

  • The FL3 plots likewise label problem sizes from C4 through C12 and include solver series such as DW2X, HFS, in-house SA, and an_ss_ge_.Source: §D.2 · p. 25

D.3 RAN1

The supplied RAN1 appendix passages identify problem-size labels and solver-series labels, but do not provide readable result comparisons.

D.3 RAN1

  • The supplied RAN1 plot labels include problem sizes from C4 through C12.Source: §D.3 · p. 26
  • The supplied RAN1 passages do not state the plotted metric values or which solver performs best.Source: §D.3 · p. 26
  • The visible RAN1 solver labels include DW2X, HFS, in-house SA, an_ms_r1_nf, and an_ss_ge_.Source: §D.3 · p. 26

D.4 RAN3

The supplied figure text labels problem sizes from C4 to C12 and lists DW2X, HFS, and in-house SA as solvers; it provides no readable performance values.

D.4 RAN3

  • The problem-size labels run from C4 through C12.Source: §D.4 · p. 27
  • The solver labels are DW2X, HFS, and SA (in-house).Source: §D.4 · p. 27

D.5 RAN7

The supplied figure text labels problem sizes from C4 to C12 and lists DW2X, HFS, and in-house SA as solvers; it provides no readable performance values.

D.5 RAN7

  • The problem-size labels run from C4 through C12.Source: §D.5 · p. 28
  • The solver labels are DW2X, HFS, and SA (in-house).Source: §D.5 · p. 28

D.6 RAN127

The supplied figure text labels problem sizes from C4 to C12 and lists DW2X, HFS, and in-house SA as solvers; it provides no readable performance values.

D.6 RAN127

  • The problem-size labels run from C4 through C12.Source: §D.6 · p. 29
  • The solver labels are DW2X, HFS, and SA (in-house).Source: §D.6 · p. 29

Related papers

Loading 1508.05087v1…