PaperlayerView exact revision on arXiv

Source-linked AI summary

Modernizing Quantum Annealing using Local Searches

Nicholas Chancellor

arXiv:1606.06833v6quant-ph

TL;DR

The standard quantum annealing algorithm is a global search, unlike modern classical optimization methods that can adapt based on intermediate results. This paper proposes controllable local quantum searches as subroutines for hybrid algorithms and analogues of parallel tempering and population annealing. It argues that these searches can reduce sensitivity to problem mis-specification, while noting that high-fidelity state reprogramming may require updated or alternative hardware.

  • Problem

    The QAA is a global search that cannot readily use information from classical algorithms or previous runs, unlike modern classical optimization methods that exploit intermediate states.

    Source: §1 · p. 3

  • Method

    The paper proposes controllable local quantum searches around selected states, combined sequentially with classical searches or used as subroutines in quantum analogues of population annealing and parallel tempering.

    Source: §1 · p. 4, Comparison Between Techniques · p. 6

  • Results

    The paper presents proof-of-principle numerical experiments and argues that local searches make mis-specification depend on the searched range rather than the total qubit count.

    Source: §10 · p. 24

  • Takeaways & Limitations

    Local quantum searches can be combined with classical algorithms and may remain meaningful when mis-specification prevents the global optimum from being correctly specified.

    Source: §1 · p. 4

    High-fidelity end-of-anneal state programming may not be possible on current D-Wave devices, though design changes or other transverse-field Ising hardware could make it feasible.

    Source: §8 · p. 22

Abstract

from arXiv · show

I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm. Such protocols will have numerous advantages over simple quantum annealing. By using such searches the effect of problem mis-specification can be reduced, as only energy differences between the searched states will be relevant. The quantum annealing algorithm is an analogue of simulated annealing, a classical numerical technique which has now been superseded. Hence, I explore two strategies to use an annealer in a way which takes advantage of modern classical optimization algorithms. Specifically, I show how sequential calls to quantum annealers can be used to construct analogues of population annealing and parallel tempering which use quantum searches as subroutines. The techniques given here can be applied not only to optimization, but also to sampling. I examine the feasibility of these protocols on real devices and note that implementing such protocols should require minimal if any change to the current design of the flux qubit-based annealers by D-Wave Systems Inc. I further provide proof-of-principle numerical experiments based on quantum Monte Carlo that demonstrate simple examples of the discussed techniques.

note added after publication

The author adds previously omitted related work on incorporating guesses into an adiabatic protocol and two machine-learning papers, while noting that the first protocol differs from the one proposed here.

note added after publication

  • The cited related protocol incorporates guesses into a closed-system adiabatic approach, though the author says it differs from this paper’s proposal.The author says the connection is close enough to warrant citation.Source: note added after publication · p. 2
  • Two machine-learning works identified for the introduction address effective-temperature estimation in quantum annealers and quantum-assisted learning of graphical models [3].The first is a case study with possible deep-learning applications; the second concerns arbitrary pairwise connectivity.Source: note added after publication · p. 2

1. Introduction

The introduction asks whether quantum annealers can gain from modern classical optimization methods, given that the standard QAA is a global search and does not readily incorporate information from prior runs. It proposes controllable local searches as quantum building blocks that can be combined with classical algorithms and may reduce sensitivity to problem mis-specification.

1. Introduction

  • The paper focuses on the transverse-field Ising model, while arguing that its approach can extend to other search spaces using a more general distance measure.In this model, Hamming distance between bitstrings counts the edges between states in the hypercube.Source: §1 · p. 3
  • The QAA is a single monotonic anneal analogous to simulated annealing, while advanced classical methods such as parallel tempering and population annealing offer other optimization strategies.Quantum annealing applications also include sampling approximate Boltzmann distributions.Source: §1 · p. 3
  • The current QAA is a global search that offers no obvious way to incorporate information from classical algorithms or previous runs, and its intermediate state cannot be determined or manipulated as in simulated annealing.Classical methods can exploit known intermediate states through population annealing or parallel tempering.Source: §1 · pp. 3–4
  • The paper proposes local quantum searches around user-selected states, with controllable range and classical input and output, allowing them to combine with classical or quantum searches.This input-output structure avoids the no-cloning obstacle to combining search steps; related work had considered the idea in limited scope.Source: §1 · p. 4
  • Local searches are argued to be less sensitive to problem mis-specification because only errors affecting states within the searched subspace are relevant.The typical random energy differences induced by such errors scale as √N for N qubits, while local searches cover only a small part of the solution space.Source: §1 · p. 4

2. Optimization and Sampling Techniques

This section reviews classical and quantum optimization and sampling methods to frame the paper’s approach. It contrasts the QAA’s single anneal with classical methods that adapt searches based on performance, motivating quantum-search analogues of those methods.

Optimization and Sampling Techniques

  • Metropolis updates accept energy-lowering moves and probabilistically accept energy-increasing moves, and detailed balance allows their use for thermal sampling or ground-state search.The acceptance probability for an energy increase is exp(−∆E/T).Source: §2 · pp. 4–5
  • Simulated annealing repeatedly applies Metropolis spin flips while lowering temperature to zero.It models a spin system cooled under classical dynamics.Source: Simulated Annealing (SA) · p. 5
  • Parallel tempering evolves multiple replicas at fixed temperatures and probabilistically swaps temperatures, letting poorly performing copies explore broadly and better-performing copies search locally.The section states that it improves substantially over simulated annealing and has no known physical analogue.Source: Parallel Tempering · p. 5
  • Population annealing evolves multiple replicas at one temperature, gradually lowers that temperature, and probabilistically deletes poor copies and replicates good ones while controlling population size.It can abort poor searches, improves substantially over simulated annealing, and has performance gains comparable to parallel tempering.Source: Population Annealing · p. 5
  • Quantum random walks evolve under a fixed quantum Hamiltonian, and the proposed local search becomes a localized-starting-condition quantum random walk under instantaneous annealing.The latter is subject to noise from a fixed-temperature bath.Source: Quantum Random Walk · p. 6
  • The QAA slowly reduces quantum fluctuations in a single monotonic anneal, making it analogous to simulated annealing rather than methods that can abort poor searches.The paper considers both closed-system adiabatic evolution and open-system transitions toward lower-energy states, and notes potential use for thermal sampling under some circumstances.Source: Quantum Annealing Algorithm (QAA) · pp. 5–6, Comparison Between Techniques · p. 6

3. Hybrid Computing

The section motivates combining classical and quantum searches because barriers of different widths may favor different search mechanisms. It proposes sequentially passing states among algorithms, including local quantum searches, to exploit this complementarity.

3. Hybrid Computing

  • A mixed landscape may contain broad smooth barriers that hinder QAA tunneling as well as rough regions with thin barriers that quantum tunneling can explore effectively.The schematic illustrates classical search crossing smooth features before quantum tunneling explores rough parts of the landscape.Source: §3 · p. 7, Figure 1 · p. 8
  • Sequential search can pass intermediate states among classical and quantum algorithms, including Monte Carlo methods and genetic algorithms.The proposed scheme requires stages that accept one or more input values and search from them.Source: §3 · p. 7
  • The section distinguishes interspersed classical and local quantum searches from later protocols in which searches are quantum mechanical and classical control selects subsequent ranges.The classical control structure chooses which local searches to perform and at what range.Source: §3 · pp. 7–8

4. How much to Search

The section treats local-search range as a control for combining quantum searches with classical optimization strategies. It describes adaptive range selection and quantum analogues of parallel tempering and population annealing.

4. How much to Search

  • The control parameter s′ sets local-search range, from no search at s′ = 1 to a global search at s′ = 0.The relation between s′ and mean Hamming distance explored is assumed to increase monotonically as s′ decreases, but may depend on the Hamiltonian and initial state.Source: §4 · p. 8
  • Observed Hamming distances can guide s′ toward a desired search radius; bisection requires logarithmically many runs in the target accuracy.The range-to-distance relation need not be known in advance; the typical distance can be estimated experimentally.Source: §4 · p. 9
  • The transverse-field strength supplies an effective-temperature proxy for choosing search ranges, but it may not approximate the temperature of observed outputs.The proxy is intended to represent fluctuation strength associated with tunneling.Source: §4 · p. 10
  • The parallel-tempering analogue swaps replicas across s′ values using lowest-found energy as a measure of local-minimum depth, favoring broader searches in shallow minima and focused searches in deep ones.Each replica’s state is defined as the lowest-energy state found in its previous annealing run.Source: §4 · pp. 10–11
  • Because the effective temperature is not an actual temperature, this parallel-tempering analogue does not obey detailed balance exactly, though classical post-processing can support approximate sampling.Source: §4 · p. 11
  • The population-annealing analogue normalizes energy-based replication so the mean replica count stays constant, preferentially applying shorter-range searches to regions with deep local minima.It progresses toward larger s′ values and lower effective temperatures.Source: §4 · p. 11

5. Local Search on an Annealer

A local annealing call starts from a chosen classical state, explores its neighborhood with a controlled transverse field, and returns a state; repeated calls can serve as subroutines for quantum analogues of population annealing and parallel tempering.

5. Local Search on an Annealer

  • The quantum parallel-tempering analogue applies local annealer calls to states at different s′ values and uses energy- and s′-dependent swap probabilities.Each call extracts a lowest-energy state and minimum energy; the algorithm considers pairwise swaps between parameter settings.Source: §5 · p. 12
  • Starting from a specified state, the protocol lowers s to s′, optionally waits, then returns to s = 1; at finite temperature, detailed balance favors lower-energy states.Repeating the cycle at a fixed s′ and initial state yields samples from a probabilistic local quantum search.Source: §5 · pp. 12, 15, Figure 3 · p. 15
  • The quantum population-annealing analogue reweights states by energy between successive s′ values and draws Poisson-distributed copy counts to form the next population.The procedure appends copies of each state and its energy to the updated population.Source: §5 · p. 13
  • The transverse-field strength controls locality: stronger A(s) relative to B(s) makes the search less local, while tunneling between perturbed states is exponentially suppressed with Hamming distance.The expansion is around a classical state, and tunneling provides the quantum mechanism for moves between nearby classical states.Source: §5 · p. 14
  • Local quantum searches relinquish quantum advantage for long-range moves, while classical methods such as parallel tempering or population annealing can handle those moves.The proposed rationale is that even a small quantum advantage in local search could improve on the underlying classical algorithm.Source: §5 · p. 14
  • The desired starting state can be prepared with standard QAA using a simple Hamiltonian, then the problem Hamiltonian is programmed before annealing to s′ and reading out.The initialization Hamiltonian is a gauge transform of an unfrustrated ferromagnet in a field, chosen to give the target state a simple landscape and a relatively large gap to the first excited state.Source: §5 · pp. 14–15

6. Proof of Principle

Proof-of-principle PIQA experiments show that local-search range can be controlled and that an intermediate local-tunneling regime can find a ground state missed by traditional annealing, while the study does not establish a scaling advantage.

6.1. methods

  • The proof-of-principle simulations use PIQA, approximating a quantum partition function with coupled classical copies and local updates; they use P = 60 slices at T = 0.05.PIQA does not simulate system-bath interactions, although its local updates approach a Boltzmann distribution relative to a quantum Hamiltonian.Source: §6.1 · p. 16
  • The test adds δ couplers to a previously studied Hamiltonian to roughen its landscape; Figure 4 specifies the couplers and fields and plots simulated-annealing success across δ.The study uses a linear schedule A(s) = 1 − s, B(s) = s; the added couplers make this problem easier for PIQA, though standard PIQA remains relatively poor in the examined regime.Source: §6.1 · p. 16, Figure 4 · p. 17
  • The calculations are proof of principle, not evidence of scaling advantage: the small problem is solvable by exhaustive search in under a second, and simulation parameters were not matched to device settings.The Hamiltonian can in principle be implemented on a D-Wave Chimera graph.Source: §6.1 · pp. 16–17

6.2. results

  • Hamming distance from the starting ground state grows as s′ decreases until the backward-annealing trajectory merges with traditional PIQA, so s′ and annealing rate control the typical search range.Figure 5 plots Hamming distance against A/B and distinguishes reverse-annealing runs by their τ_PIQA values, alongside a dashed forward-annealing run.Source: Figure 5 · p. 17, §6.2 · p. 18
  • Local tunneling raises ground-state success above the frozen-regime level, but too-large A(s′)/B(s′) tunnels into false minima and lowers success; none of 1,000 traditional PIQA runs found the ground state.The authors present the local-search example as proof of principle that local exploration can succeed when a global search fails.Source: §6.2 · p. 18

7. Applications to Sampling

Quantum local searches can support approximate sampling of local minima, but their outputs are not generally thermal samples without further processing. The section also outlines ways to estimate or recover thermal weights.

Parallel tempering analogue

  • The parallel-tempering analogue may approximately sample local minima, but annealing each call to s = 1 prevents its raw outputs from approximating a thermal sample unless that step is very fast.The raw states can still give very approximate relative thermal probabilities across minima, with quantum fluctuations serving as a rough proxy for thermal fluctuations.Source: §7 · p. 18

Local-search sampling

  • Figure 6 reports three regimes as A(s′)/B(s′) changes: frozen behavior, enhanced ground-state finding through local tunneling, and global tunneling that often traps the state in a false minimum.The regimes are based on 500 random starting points subjected to the same classical pre-anneal; error bars are one standard deviation of the mean.Source: §7 · p. 19, Figure 6 · p. 19

Parallel tempering analogue

  • Applying Metropolis rules at T = Teff to the outputs can produce an approximate thermal sample within each local minimum.The proposed procedure first collects outputs at the desired Teff, potentially discarding early iterations as warm-up.Source: §7 · p. 19

Population annealing analogue

  • For estimating the relative importance of local minima, mean run energy may be more appropriate than the minimum energy found.The same substitution may improve population-annealing estimates of thermal weights and replica-copy decisions.Source: §7 · p. 19

Hybrid sampling

  • For the generalized hybrid algorithm, estimating thermal weights remains unclear; estimating entropy and free energy for disjoint minima through Monte Carlo specific-heat integration is proposed as a possible route.The hybrid algorithm may identify more low-energy local minima than other methods but does not itself indicate their relative thermal weights.Source: §7 · p. 19

Sampling post-processing

  • If fast annealing were available, post-processing would not be needed for either analogue because the distribution within each disjoint minimum would already have the desired quantum Boltzmann-machine form.This is conditional on fast annealing being available.Source: §7 · pp. 19–20

8. How to avoid solving the wrong problem

Local searches can reduce the relevance of problem mis-specification by limiting which energy differences determine the selected state. The section discusses the reprogramming capability needed to implement such searches and the unresolved feasibility of doing so on current D-Wave devices.

Problem mis-specification

  • Unlike a local search, the global QAA can be disrupted by corruption anywhere in the energy landscape, making control precision a scaling concern.The typical random energy shift from mis-specification scales as √N; sufficiently strong errors can make the optimum of the implemented Hamiltonian differ from the target optimum.Source: §8 · p. 20
  • A local search depends on energy differences among explored states, so mis-specification shifts in unsearched states do not affect which explored state is optimal.Overall energy shifts shared by reachable states are also irrelevant.Source: §8 · p. 20
  • Under a roughly hypercubic explored subspace, fixing the search range can remove the direct dependence of mis-specification error on total system size, though it also bounds where a quantum advantage could occur.The effective typical shift is described as proportional to p h(s′).Source: §8 · pp. 20–21
  • Local searches can remain valid for arbitrarily large Hamiltonians provided each search stays within a sufficiently small subspace.This is the stated scope condition for the large-system claim.Source: §8 · p. 21

Implementation feasibility

  • The protocol requires programming the machine's final classical state, but does not require changing the parts of the protocol where quantum mechanics plays a role.The state need not be protected as a delicate superposition during reprogramming.Source: §8 · p. 21
  • Reprogramming at s = 1 must preserve the classical bit state; D-Wave's bistable regime suppresses tunneling, while added barrier height or slower reprogramming may mitigate thermal excitation.Strong field terms during coupler reprogramming are also suggested as a way to stabilize the state.Source: §8 · pp. 21–22
  • Current D-Wave devices have not been experimentally tested for state disruption during reprogramming, although low-level controls exist to attempt the protocol without physical modification.Higher-fidelity reprogramming and reduced reprogramming time and cooling demands would be desirable beyond proof of principle.Source: §8 · p. 22
  • If high-fidelity reprogramming is infeasible on current D-Wave devices, design changes or other transverse-field Ising hardware may make it feasible.The circuit architecture uses loop fluxes to control the effective potential experienced by the flux φ.Source: §8 · p. 22, Figure 7 · p. 23

10. Conclusions

The paper proposes using quantum annealers for local rather than global searches, and combines these searches with classical optimization strategies. It argues that this can reduce sensitivity to problem mis-specification and supports hybrid optimization and sampling, while numerical experiments provide proof of principle.

Conclusions

  • The proposed protocol performs local rather than global searches, making the effect of problem mis-specification depend on search range rather than total qubit count.The paper argues that this can remain useful when noise would ruin a global QAA search.Source: §10 · p. 24
  • Sequential quantum and classical searches can form hybrid algorithms, and the paper constructs quantum-subroutine analogues of parallel tempering and population annealing.The author argues that algorithmic improvement may be possible even with only a small quantum advantage in local searches.Source: §10 · p. 24
  • The proposed techniques also apply to sampling with appropriate post-processing, and simple numerical experiments demonstrate the underlying principles.The protocol may be feasible on current devices without alterations.Source: §10 · p. 24

Appendix: Path Integral Quantum Annealing

The appendix describes the path-integral quantum annealing procedure used for the numerical results and specifies its time-step update.

Appendix: Path Integral Quantum Annealing

  • The numerical experiments use Path Integral Quantum Annealing procedures from, with the appendix noting similarities and differences needed to reproduce the results.Source: Appendix: Path Integral Quantum… · p. 24
  • Each Monte Carlo time step attempts a classical cluster update for every spin, flipping that spin simultaneously across all Trotter slices.The time parameter τP IQA counts Monte Carlo steps per spin.Source: Time Parameter τP IQA · p. 24

Starting Conditions for Traditional QAA

Traditional QAA runs began at A/B = 3 rather than B = 0 to prevent the Trotter slices from becoming completely uncorrelated, following.

Starting Conditions for Traditional QAA

Classical Pre-anneal

PIQA runs used a classical pre-anneal to establish initial states, with shared pre-anneal states in comparisons to reduce statistical noise. The resulting error bars may overstate relative variation between Fig. 6 points.

Classical Pre-anneal

  • PIQA pre-annealing used 100 Monte Carlo sweeps on the classical Hamiltonian before initializing all Trotter slices in the resulting state.Source: Classical Pre-anneal · p. 25
  • The pre-anneal temperature was Tclass = P T for runs starting at A/B = 3, and Tclass = T for runs starting with B ≫ A.Source: Classical Pre-anneal · p. 25
  • The breaking of uniform Trotter-slice initialization likely caused the numerical artefact near A/B = 3 in Fig. 5’s dashed line.Source: Classical Pre-anneal · p. 25
  • A single classical pre-anneal supplied the shared initial states for multiple PIQA runs plotted from s = 1, removing noise from finding different classical states.Source: Classical Pre-anneal · p. 25
  • Fig. 6 error bars show absolute statistical variation, so relative variation between points is probably substantially smaller, though difficult to estimate precisely.Source: Classical Pre-anneal · p. 25

Related papers

Loading 1606.06833v6…