PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

Elizabeth Crosson, Aram W. Harrow

arXiv:1601.03030v2quant-phcond-mat.stat-mechcs.DSmath.PR

TL;DR

The paper asks whether SQA can match QA’s performance on the spike problem, where SA encounters an exponential barrier. It uses a Markov-chain comparison method to analyze SQA and proves polynomial-time sampling and optimization for α + ζ < 1/2. The result shows an exponential speedup over SA on this particular problem, while the authors limit their proof to a specific parameter range.

  • Problem

    The performance of SQA is difficult to establish generally, including whether it can achieve QA’s advantage over SA on the spike problem.

    Source: §1 · pp. 2–3

  • Method

    The proof compares the SQA chain with an easier spikeless chain using canonical paths on a good subset and a warm start along the adiabatic path.

    Source: Proof Outline · p. 4

  • Results

    For α + ζ < 1/2, SQA efficiently samples the QA output distribution, with running time ˜O(n^7) for worldline updates or ˜O(n^17) for single-site flips.

    Source: §1 · p. 3

  • Takeaways & Limitations

    SQA achieves an exponential speedup over SA on this particular problem, so the tunneling benefit need not be exclusively quantum.

    Source: §1 · p. 3

    The proof does not bound SQA convergence when α + ζ > 1/2.

    Source: Discussion · p. 5

Abstract

from arXiv · show

Simulated Quantum Annealing (SQA) is a Markov Chain Monte-Carlo algorithm that samples the equilibrium thermal state of a Quantum Annealing (QA) Hamiltonian. In addition to simulating quantum systems, SQA has also been proposed as another physics-inspired classical algorithm for combinatorial optimization, alongside classical simulated annealing. However, in many cases it remains an open challenge to determine the performance of both QA and SQA. One piece of evidence for the strength of QA over classical simulated annealing comes from an example by Farhi, Goldstone and Gutmann . There a bit-symmetric cost function with a thin, high energy barrier was designed to show an exponential seperation between classical simulated annealing, for which thermal fluctuations take exponential time to climb the barrier, and quantum annealing which passes through the barrier and reaches the global minimum in poly time, arguably by taking advantage of quantum tunneling. In this work we apply a comparison method to rigorously show that the Markov chain underlying SQA efficiently samples the target distribution and finds the global minimum of this spike cost function in polynomial time. Our work provides evidence for the growing consensus that SQA inherits at least some of the advantages of tunneling in QA, and so QA is unlikely to achieve exponential speedups over classical computing solely by the use of quantum tunneling. Since we analyze only a particular model this evidence is not decisive. However, techniques applied here---including warm starts from the adiabatic path and the use of the quantum ground state probability distribution to understand the stationary distribution of SQA---may be valuable for future studies of the performance of SQA on cost functions for which QA is efficient.

1 Introduction

The paper proves polynomial-time performance for standard SQA on the spike cost function when α + ζ < 1/2, a setting where simulated annealing faces an exponential barrier. It develops a Markov-chain comparison approach and discusses the bounds and extensions that remain open.

1 Introduction

  • SA with moves flipping fewer than n^ζ bits faces an exponentially unlikely uphill move at the spike, while SQA is proposed as a classical optimizer to compare with both SA and QA.The paper notes that the spike is a toy problem with exploitable structure, while algorithm comparisons are intended to assess general-purpose implementations.Source: §1 · pp. 2–3

Previous Work

  • Rigorous QMC efficiency results were known for limited settings, while comparing SQA with QA was largely restricted to small systems or analytically solvable models.The paper identifies few general conditions guaranteeing polynomial-time convergence.Source: §1 · p. 3, Previous Work · p. 4

1 Introduction

  • For α + ζ < 1/2, standard SQA finds the spike minimum in polynomial time, sampling the QA output distribution in ˜O(n^7) with worldline updates or ˜O(n^17) with single-site flips.The authors describe SQA as obtaining an exponential speedup over SA for this particular problem.Source: §1 · p. 3

Proof Outline

  • The proof compares the spike chain with an easier spikeless chain, using canonical paths on a good subset and a warm start along the adiabatic path.States spending too much time on the spike are excluded by bounding spike-time moments using properties of the quantum system.Source: Proof Outline · pp. 4–5

Discussion

  • The proof does not bound SQA convergence when α + ζ > 1/2, and extending the comparison to broader barriers requires better understanding of their wave functions and spectral gaps.The authors conjecture efficiency for some out-of-range parameters, but say extensions of their techniques are needed.Source: Discussion · pp. 5–6
  • The authors suggest most-paths comparison may also apply to weakly repulsive particle systems, where rare crowded configurations need not significantly worsen mixing.They conclude that SQA’s advantage over SA on the spike means tunneling benefits need not be exclusively quantum.Source: §1 · p. 3, Discussion · p. 6

2 Background

Quantum annealing encodes a cost function in a final Hamiltonian and evolves from a transverse-field initial state along an adiabatic path. Simulated quantum annealing uses a path-integral representation and Markov chains to sample the system’s thermal state along that path.

2.1 Quantum annealing

  • The ground state of the final cost Hamiltonian corresponds to the bit string minimizing the cost function.The system starts in the ground state of a uniform transverse field and interpolates between the initial and final Hamiltonians as the adiabatic parameter runs from 0 to 1.Source: §2.1 · p. 7
  • At finite temperature, quantum annealing targets the equilibrium thermal state, and the simulation aims to reproduce its computational-basis distribution.The paper assumes the inverse temperature is sufficiently large for the system to remain close to the ground state.Source: §2.1 · p. 7

2.2 Simulated quantum annealing

  • The path-integral representation expresses the partition function as a sum over trajectories of time-slice bit strings, with a Suzuki-Trotter approximation used to separate non-commuting terms.For the spike cost function, the paper takes δ = n^-1, giving L = O(n^2β^(3/2)), and treats the approximation error as negligible for convergence-time analysis and the sampled distribution.Source: §2.2 · pp. 8–9
  • SQA discretizes the adiabatic path and samples the stationary distribution π over n worldlines of L bits at successive parameter values.The marginal on the first time slice gives the distribution associated with the quantum thermal state.Source: §2.2 · p. 9
  • The analyzed chains use either single-site Metropolis flips or heat-bath updates that resample one qubit’s worldline.Single-site moves flip one of nL bits; worldline updates can be implemented efficiently and allow runtime scaling polylogarithmically with L.Source: §2.2 · p. 9
  • At s = 1, local-move transitions disconnect the state space, while for s < 1 the stationary distribution is supported throughout it.As s approaches 1, local moves can also suffer critical slowing down, motivating cluster updates and the analysis of worldline updates.Source: §2.2 · p. 9
  • SQA runtime at each path value depends on Markov-chain mixing time, which is commonly bounded using the transition matrix’s spectral gap.The standard mixing bounds are worst-case over starting states; the paper develops methods for cases where some starts may mix inefficiently.Source: §2.2 · p. 10

3 Incomplete sets of canonical paths

The section develops a comparison strategy for Markov chains that remain comparable on a large good subset despite severe differences elsewhere. It uses that strategy and a filled-in chain to control leakage and establish rapid mixing.

3 Incomplete sets of canonical paths

  • The method tolerates bad vertices as if they trap the walker, yet shows the overall algorithm works with high probability.The comparison is designed for chains that are comparable on a subset carrying most of their stationary probability.Source: §3 · p. 10, §3.2 · p. 11

3.1 Markov chains and the path comparison method

  • Path comparison bounds a chain’s gap through congestion, the total flow load on edges along the chosen paths.The section reviews canonical path and flow variants, including comparisons to a complete graph with the same stationary distribution.Source: §3.1 · p. 11

3.2 Most-paths comparison

  • For the spiked and spikeless SQA chains, configurations with exponentially small stationary-probability ratios are excluded from the good set.The transition-probability ratio R is O(1) for the transition types considered in the application.Source: §3.2 · pp. 11–12
  • The good set is mostly well connected: each good vertex has at least 2/3 of its conditional mass among good neighbors.Even pairs without a path avoiding bad edges can be routed through a shared set of measure at least 1/4, yielding flows with controlled congestion.Source: §3.2 · pp. 12–13

3.3 Leaky random walks

  • The filled-in chain mixes rapidly, while its behavior differs from the restricted walk only when leakage occurs.The coupling equates leakage probability with the restricted walk’s probability of having visited the bad set; leakage grows linearly with time while distance to stationarity decreases exponentially. A bound on the restricted chain alone does not establish a gap bound for the original chain.Source: §3.3 · pp. 13–14

4 Efficient convergence of SQA for the spike cost function

The analysis establishes polynomial-time convergence for SQA on the spike cost function by comparing the spiked chain with a tractable spikeless chain and warm-starting along the adiabatic path. It bounds the time spent on the spike and the mixing time within a good set, yielding polynomial total runtime for both update schemes.

4 Efficient convergence of SQA for the spike cost function

  • The proof compares the spiked SQA chain with a spikeless chain, excluding states with excessive spike time to obtain paths through a good set.The spikeless chain consists of non-interacting 1D ferromagnetic Ising models; the spike-free chain's canonical paths are used to bound congestion.Source: §4 · pp. 15–16
  • Single-site updates incur a large polynomial overhead when the transverse field is small, because of strong imaginary-time interactions.The bound nevertheless remains polynomial in the spike-system analysis.Source: §4 · p. 16
  • The spikeless ground-state probability over Hamming weights is binomial, enabling bounds on spike occupancy and its higher moments.The moment bound is used with m=c/ϵ to control the probability of states spending too much time on the spike.Source: §4 · pp. 17, 19
  • A discretized adiabatic path supplies warm starts, with successive stationary distributions chosen to satisfy the warm-start condition.The path uses a step size ∆s selected so adjacent distributions have pointwise ratio at most 2.Source: §4 · p. 19
  • Within the good set, the worldline-update chain has mixing time O(n^3β log n), while the leaky walk remains close to stationarity before escape.Choosing c=2+q+log(1/δ) makes the distance at most δ for times from the mixing time through Θ(n^q).Source: §4 · p. 20
  • The total runtime is ˜O(n^7) with single-qubit worldline updates and ˜O(n^17) with single-site Metropolis updates.The worldline bound follows from ˜O(n^6β^4); the single-site analysis gives the larger polynomial bound.Source: §4 · p. 20
Loading 1601.03030v2…