PaperlayerView exact revision on arXiv

Source-linked AI summary

What is the Computational Value of Finite Range Tunneling?

Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, Hartmut Neven

arXiv:1512.02206v4quant-ph

TL;DR

The paper asks whether finite-range tunneling can provide computational value in quantum annealing beyond classical thermal escape. It benchmarks physical QA against SA and QMC on rugged optimization problems, finding large advantages for QA on crafted instances and better scaling for QA-simulation methods than SA on number partitioning.

  • Problem

    The paper examines whether finite-range tunneling can yield computational advantages, including for higher-order binary optimization problems that current annealers cannot directly represent.

  • Method

    The authors benchmark D-Wave 2X against SA and QMC on weak-strong cluster networks, and numerically study QMC and algorithmic tunneling on random number-partitioning instances.

  • Results

    For nearly 1000-variable crafted problems, QA was more than 10^8 times faster than single-core SA, while QA and QMC had comparable scaling but could differ by factors as high as 10^8.

  • Takeaways & Limitations

    Finite-range tunneling may provide runtime advantages on rugged landscapes, and the authors expect relevance for higher-order binary optimization as annealer hardware improves.

Abstract

from arXiv · show

Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to Simulated Annealing (SA). For instances with 945 variables, this results in a time-to-99%-success-probability that is $\sim 10^8$ times faster than SA running on a single processor core. We also compared physical QA with Quantum Monte Carlo (QMC), an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X again runs up to $\sim 10^8$ times faster than an optimized implementation of QMC on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a timescale comparable to the D-Wave 2X. However, we believe that such solvers will become ineffective for the next generation of annealers currently being designed. To investigate whether finite range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that QMC, as well as other algorithms designed to simulate QA, scale better than SA. We discuss the implications of these findings for the design of next generation quantum annealers.

I. INTRODUCTION

Quantum annealing offers tunneling as an escape route from local minima, potentially overcoming tall, narrow barriers more efficiently than simulated annealing. The paper studies finite-range tunneling, its comparison with QMC, and its limitations for wide-barrier gaps.

  • Quantum annealing can penetrate energy barriers without increasing energy, unlike simulated annealing, which must thermally climb over them.This tunneling mechanism motivates QA as a heuristic for optimization.
  • QA dynamics are governed by an annealing schedule that begins with strong transverse-field-driven quantum fluctuations and ends with the problem Hamiltonian dominant.The schedule uses smooth functions A(t) and B(t), with opposite dominance at the beginning and end.
  • For sufficiently tall and narrow barriers, QA can overcome barriers exponentially faster than SA, whose escape time grows exponentially with barrier height ΔE.The tunneling domain size D controls the exponential dependence of annealing time.
  • QMC reproduces the physical tunneling exponent in specific cases but can incur a computational prefactor overhead of many orders of magnitude when the tunneling range is finite.The relevant runtime forms are T_QMC = B_QMC e^(αD), with finite D independent or weakly dependent on problem size.
  • Finite-range tunneling is expected to help across narrow-barrier gaps while failing to prevent diabatic transitions associated with very small gaps across wide barriers.The latter can include the gap between the ground and first excited states.

A RUGGED ENERGY LANDSCAPE

The paper benchmarks finite-range tunneling on weak-strong cluster networks engineered with rugged landscapes and tall barriers. D-Wave 2X substantially outperforms SA on the largest tested instances, while comparisons with QMC use single-core classical runtime estimates.

  • Weak-strong cluster construction: Weak-strong cluster pairs use two Chimera unit cells with ferromagnetic couplings, a strongly pinned cluster, and a weaker cluster controlled by h1.For h1 = 0.44 < 1/2, the weak cluster reverses during annealing and aligns with the strong cluster.
  • Weak-strong cluster construction: Weak-strong cluster networks connect strong clusters with randomly chosen ferromagnetic or antiferromagnetic couplings to create scalable rugged instances.The benchmark layouts include sizes of 296, 489, and 945 qubits, subject to hardware availability.
  • D-Wave versus Simulated Annealing: 1.8 · 10^8 faster at 945 variables, the D-Wave 2X processor outperformed SA in time to reach the ground state with 99% success probability.The comparison measures SA runtime on a single core and uses tuned schedules and restart counts.
  • Benchmark scope: The benchmark advantage is specific to engineered finite-range-cotunneling instances; random Ising instances with low energy barriers provide a different landscape.The weak-strong cluster networks were designed to cause SA failure.

B. D-Wave versus Quantum Monte Carlo

The study compares path-integral QMC with D-Wave on the same benchmark, finding similar scaling but a large QMC computational overhead from its prefactor and worldline updates.

  • QMC samples a classical Hamiltonian approximating the transverse-field Ising model, using replicas along imaginary time.Continuous path-integral QMC avoids discretization errors associated with a finite number of Trotter slices.
  • QMC effort is measured as nsweeps×N×Tworldline and is evaluated for 99% ground-state success on a single CPU core.The sweep count is optimized across quantiles and system sizes, while Tworldline depends on the annealing schedule.
  • The physical-tunneling exponent is identical for QMC and D-Wave in this benchmark, but QMC has a very substantial runtime prefactor overhead.The overhead matters because the cotunneling domain D is finite or depends only weakly on problem size.
  • Between some quantiles and system sizes, the prefactor advantage reaches 10^8 in favor of D-Wave.

C. D-Wave versus other Classical Solvers

The paper places D-Wave’s benchmark performance against classical alternatives and develops an instanton picture of multispin tunneling. It concludes that current comparisons do not establish quantum speedup, while future denser hardware may change the classical-solver balance.

  • C. D-Wave versus other Classical Solvers: Heuristic classical solvers outperform SA, QMC, and D-Wave 2X on most Chimera instances, so the benchmark does not establish quantum speedup.The Hamzede Freitas-Selby algorithm uses large-neighborhood optimizations and avoids the barrier in weak-strong cluster pairs.
  • C. D-Wave versus other Classical Solvers: Future higher-degree connectivity may make cluster finding too costly, while multiqubit cotunneling is not limited to sparse graphs.
  • C. D-Wave versus other Classical Solvers: The paper cautions that finite-size runtime extrapolation can misidentify asymptotic behavior, and hardware changes can alter constant separations between algorithms.The authors report that older-chip extrapolation predicted 10^4 speedup at 1000 variables but observed more than 10^8.
  • A. Instantons in systems with multiple spins: Cotunneling changes a group of spins simultaneously at energies well below mean-field potential barriers.The tunneling path is analyzed with an imaginary-time path integral and minimum action.
  • A. Instantons in systems with multiple spins: For a domain of D spins, the low-temperature instanton action scales as Smin=Damin when spin contributions remain correlated.
  • A. Instantons in systems with multiple spins: The instanton framework treats collective tunneling under a transverse-field Hamiltonian, including cases where total spin is not conserved.

B. Tunneling simulation in QMC

Path-integral QMC simulates multispin tunneling by adding an imaginary-time dimension, but this representation introduces classical computational overhead. Its exponential sweep dependence can match QA while its prefactors differ substantially.

  • QMC introduces an extra imaginary-time dimension and represents each spin trajectory as a worldline with M Trotter replicas.Sampling this extra dimension creates an overhead absent from the corresponding quantum dynamics.
  • QMC runtime is organized into factors including problem size, sweep count, and worldline-update time.The computational effort is expressed as TQMC=N nsweeps Tworldline.
  • The sweep count scales as nsweeps ∝e^(αD), where D is the typical cotunneling-domain size and α depends on inverse temperature.When D=O(N), this dependence becomes a major computational bottleneck for QMC and QA.
  • QMC and QA can share the same exponential dependence on Damin/ℏ, while their sweep prefactors, N factors, and worldline-update times differ substantially.

C. Comparison of QA and QMC for the “weak-strong cluster pair” problem

For the weak-strong cluster pair, QA and QMC share the same tunneling exponent, but QMC incurs a substantial computational overhead. The analysis accounts for success probabilities, sweep choices, and hardware timing.

  • The QA tunneling process corresponds to an avoided crossing between the two lowest energy levels, while all other levels lie substantially higher.
  • D = 8 cotunneling spins participate in the weak-strong cluster pair, within a system of N = 16 spins.The tunneling event reverses the total spin of the left cluster.
  • The QMC parameters are selected by fixing p0 = 0.95 and minimizing βnsweeps, with βsat determined from the saturation behavior.This procedure gives the minimum value of the product βnsweeps.
  • QMC success probability increases with β and saturates at a value dependent on the number of sweeps.Periodic boundary conditions performed better than open boundary conditions in this case.
  • QMC and physical QA have the same tunneling exponent, but their runtime ratio includes a substantial prefactor overhead for QMC.The overall speedup factor must also account for the number of qubits.
  • The promise of physical QA over QMC depends on coherent adiabatic evolution under the gap and suppressed thermal excitations.Fast QA schedules and operation at 5 mK require improvements in control electronics and readout.

IV. NUMERICAL STUDIES OF QUANTUM ANNEALING FOR GENERIC PROBLEMS WITH RUGGED ENERGY LANDSCAPES

The paper evaluates QA for practical optimization problems using three criteria: valuable solutions, near-term hardware representability, and a runtime advantage.

  • A suitable quantum-annealing problem should have valuable or interesting solutions.
  • A suitable problem should be representable on hardware that can be built in the near future.
  • A suitable problem should offer a runtime advantage through quantum annealing.

A. Number Partitioning

Number Partitioning provides rugged optimization landscapes for studying tunneling, but hardware representation becomes difficult as precision requirements grow. Numerically, QMC and QA-like methods scale better than SA, while finite-range search can outperform KK heuristics over relevant sizes.

  • Number Partitioning minimizes the residue E = |P, and its low-energy landscape is extremely rugged.Random instances use independent uniformly distributed numbers, and the problem is NP-hard.
  • NPP is challenging because known heuristic methods leave residual energies far above the minimum, despite greedy and KK time complexity of N log N.
  • High-precision NPP instances violate near-term hardware representability because expressing them quadratically requires coupling-coefficient bit precision growing with N^2.The cited discussion notes that this is not a concern for numerical studies.
  • QMC and QA-like algorithms scale better than SA on NPP, consistent with tunneling being more useful than thermal transitions in rugged landscapes.Table I reports SA’s poor scaling and compares runtime exponents obtained from T ∝ 2^αN fits.
  • Algorithmic Tunneling flips groups of κ bits, selecting the flip that most reduces residual energy, and serves as an upper bound on typical QA performance.It does not model entropic effects or barrier heights.
  • For κ > α log N, Algorithmic Tunneling can reach lower costs than KK as N increases.
  • With κ = 8, Algorithmic Tunneling reaches much smaller residues than conventional heuristics across a broad range of realistic NPP sizes.For high-precision instances, NPP becomes intractable already for N > 100.
  • For α0 = 1.16 and N = 1000, the barrier length is κ = 10, while the limiting residual-energy ratio approaches zero.

B. Kth Order Binary Optimization

The paper identifies Kth-order binary optimization with K > 2 as a candidate class for practical QA studies because it is NP-hard and occurs in engineering and computational tasks.

  • Kth-order binary optimization with K > 2 is proposed as a candidate problem class satisfying the paper’s practical suitability criteria.The authors are focusing on K ∈ {4, 5, 6}.

V. DESIGNING FUTURE ANNEALERS OF PRACTICAL RELEVANCE

The paper identifies hardware representation as a major hurdle for applying QA to higher-order optimization problems. It considers physical K-body couplers and logical reductions to 2-local problems, each with substantial embedding challenges.

  • Hardware representation: K-local optimization remains difficult to represent because current annealers support only pairwise couplings, K = 2.The paper frames support for higher-order interactions as necessary for practical relevance.
  • Physical couplers: Physical K-body couplers may be difficult to lay out on two-dimensional chips or layered architectures.Implementing all possible higher-order couplings would be infeasible, while even sparse O(N) coupling sets may remain challenging.
  • Embedding constraints: Fixed-graph embedding with limited available K-local terms may itself be difficult for economically relevant problem instances.The challenge applies even when applications require only L = O(N) coupling terms.
  • Logical embeddings: Embedding K-local problems into 2-local problems introduces ancillary qubits and may alter the tall, narrow barriers required for useful tunneling.The paper treats this potential landscape distortion as its main concern about quadratic reductions.

VI. SUMMARY

The study finds large QA runtime advantages on carefully crafted rugged landscapes, while emphasizing that practical quantum-enhanced optimization still requires substantial hardware development. It also reports a large constant overhead for QMC relative to physical QA.

  • VI. SUMMARY: SA is treated as the generic classical competitor because it remains competitive when optimization problems offer little exploitable structure.The authors emphasize that expert-designed classical methods are not always readily available for complex tasks.
  • VI. SUMMARY: QA was more than 10^8 times faster than single-core SA on problems with nearly 1000 binary variables.The problems were carefully crafted with rugged landscapes dominated by large, tall barriers.
  • VI. SUMMARY: QMC had comparable runtime scaling with problem size but was separated from quantum hardware by a factor sometimes as high as 10^8.The comparison concerns the D-Wave 2X and QMC implementations used in the study.
  • VI. SUMMARY: The authors expect higher-order binary optimization with larger K to contain more practical instances benefiting from QA.This expectation is based on the increased ruggedness of higher-order energy landscapes and the role of tunneling across tall, narrow barriers.
  • VI. SUMMARY: Next-generation annealers need better connectivity density, control precision, coherence, and support for higher-order interactions.These improvements are presented as necessary for embedding practically relevant optimization problems.
  • VI. SUMMARY: The analysis is incomplete because coherent annealers could provide additional acceleration through saddle-point transitions and probability-distribution sampling.The paper limits its present focus to experimentally accessible finite-range tunneling.

Appendix A: Quantum Annealing results for Weak-Strong cluster problem with 16 qubits

The appendix models QA dynamics for the weak-strong cluster problem using experimentally informed D-Wave 2X parameters and examines transition rates, freezing, success probabilities, and QMC runtime.

  • Model and parameters: The detailed QA and incoherent multi-qubit cotunneling model was applied to updated D-Wave 2X schedules and noise parameters.The updated parameters include the schedule functions A(s), B(s), linewidth W, Ohmic coefficient η, and device temperature T.
  • Model and parameters: The annealing parameter is s = t/TQA, relating elapsed time to the total QA duration.The schedule functions define the time dependence of the annealing process.
  • QA dynamics: After the avoided crossing, W10(s) decays rapidly as the effective tunneling domain D(s) grows.This produces multi-qubit freezing, which partially traps population in the excited state during later QA stages.
  • QA dynamics: The modeled final ground-state success probability is p0 = 0.85, close to the experimentally observed mean value of 0.9.The equilibrium ground-state population exceeds the actual population for s ≳ 0.64, marking the onset of transition-rate freezing.
  • QMC comparison: QMC performance is assessed by optimizing temperature, sweeps, schedules, boundary conditions, and replica postprocessing before comparison with D-Wave 2X.The runtime estimate uses worldline updates multiplied by the time per update on a single core.
  • QA dynamics: The appendix evaluates W10(s), p0 versus temperature and QA duration, and ground- and first-excited-state occupation during QA.The time-dependent Schrödinger-equation calculation reaches success probability 0.95 at 70.9 ns.
  • QMC comparison: The optimized QMC prefactor is approximately 10^6 at the median and up to approximately 10^8 at the 85th quantile.The results are reported using the same methodology as the earlier section and are plotted in Fig. 13.
  • QMC comparison: Optimizing many QMC parameters on only 100 instances raises concerns about overlearning and becomes computationally prohibitive as problem size increases.This is a methodological limitation of the benchmark procedure.
Loading 1512.02206v4…