PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Annealing and Analog Quantum Computation

Arnab Das, Bikas K. Chakrabarti

arXiv:0801.2193v3quant-phcond-mat.stat-mechphysics.comp-ph

TL;DR

The paper addresses how hard optimization problems become trapped in rugged landscapes and how quantum fluctuations might improve exploration. It reviews mappings to spin glasses, introduces quantum spin glasses, and follows annealing by slowly reducing the tunneling term. The review reports faster quantum-annealing relaxation in some cases, improved results from suitable kinetic terms, and a framework for analog quantum computation.

  • Problem

    Hard optimization landscapes can contain many local minima and high barriers that trap classical annealing and make exhaustive search exponentially costly.

  • Method

    The review maps optimization problems to spin-glass Hamiltonians, adds a quantum kinetic term, and reduces quantum fluctuations adiabatically toward zero.

  • Results

    Quantum annealing can reach glassy ground states faster in some simulations and experiments, while suitable kinetic terms can improve results by increasing the spectral gap.

  • Takeaways & Limitations

    Quantum annealing provides a general framework for analog quantum computation of hard optimization problems through adiabatic reduction of quantum fluctuations.

Abstract

from arXiv · show

We review here the recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations. The concept is introduced in successive steps through the studies of mapping of such computationally hard problems to the classical spin glass problems. The quantum spin glass problems arise with the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.

I. INTRODUCTION

The paper frames hard discrete optimization as navigating rugged cost landscapes, then introduces quantum annealing as adiabatic reduction of quantum fluctuations to reach low-energy solutions. It connects spin glasses, combinatorial problems, and analog quantum computation.

  • Spin glasses develop rugged landscapes with many frustrated local and global minima separated by energy barriers.
  • Exhaustive search generally requires exponentially many configurations, while thermal annealing can fail when barriers become very high.
  • Quantum fluctuations can tunnel through sufficiently narrow barriers, helping systems escape local minima that impede classical thermal dynamics.
  • Quantum annealing adds a non-commuting kinetic term to the classical Hamiltonian and reduces it slowly to zero under adiabatic conditions.The intended endpoint is the ground state of the classical problem, assuming no ground-state level crossing and a ground-state initial state.
  • Quantum annealing provides a framework for analog quantum computation, complementing digital computation based on quantum logic gates.
  • Hard optimization problems minimize a cost or energy function over discrete configurations, including spin states and traveling-salesman tours.

B. Statistical Mechanics of the Optimization Problems and Thermal Annealing

This section relates combinatorial optimization to statistical mechanics: thermal annealing uses controlled noise to explore rugged landscapes, while spin-glass frustration and barriers explain slow or trapped dynamics.

  • Heuristic local minimization repeatedly accepts cost-lowering local changes but provides no guarantee of accuracy or worst-case runtime.
  • B. Statistical Mechanics of the Optimization Problems and Thermal Annealing: Thermal annealing introduces an artificial temperature, accepts uphill moves with Boltzmann-like probability, and gradually reduces the fluctuation scale.
  • B. Statistical Mechanics of the Optimization Problems and Thermal Annealing: In the limit of infinitely slow cooling, simulated annealing reaches the global minimum with certainty, while finite-time cooling can still yield useful approximations.
  • Random ferromagnetic and antiferromagnetic interactions create frustration, degeneracy, and rugged potential-energy landscapes in spin glasses.
  • Below the glass transition, systems can remain trapped in valleys separated by high free-energy barriers, restricting configuration-space exploration.
  • The scope of quantum annealing for long-range systems with replica-symmetry-breaking behavior remained an open question, with reported successes mostly involving short-range systems.

2. The Traveling Salesman Problem

The traveling-salesman problem is represented as a constrained energy-minimization problem, illustrating both thermal-annealing performance and the structure of near-optimal Euclidean tours.

  • 2. The Traveling Salesman Problem: The TSP seeks a minimum-length tour through N cities, with each instance specified by inter-city distances.
  • 2. The Traveling Salesman Problem: A tour can be encoded by constrained binary or Ising variables, with frustration arising from requirements on rows, columns, and valid tour structure.
  • 2. The Traveling Salesman Problem: TSP variants differ between finite-dimensional Euclidean distances and random distances in infinite dimension.
  • 2. The Traveling Salesman Problem: For Euclidean TSP instances, spatial locality makes large-N approximation easier through partitioning into smaller regions and joining local paths.
  • 2. The Traveling Salesman Problem: For N = 60 to N = 160, thermal annealing produced many near-optimal tours whose overlap distributions became sharply peaked as N increased.
  • 2. The Traveling Salesman Problem: 5/8 < Ω < 0.92 is an analytical bound for the average normalized optimal path length per city in two-dimensional Euclidean TSP.
  • 2. The Traveling Salesman Problem: Thermal annealing achieved normalized optimal tour length per step Ω≤0.95 for instances up to 6000 cities.

D. Quantum Spin Glasses and Annealing

Quantum spin glasses add controllable quantum fluctuations to disordered spin systems, enabling phase-diagram analysis and annealing strategies based on reducing a tunneling field. Their effectiveness depends on kinetic-term choice, spectral gaps, and unresolved phase behavior.

  • D. Quantum Spin Glasses and Annealing: A quantum spin glass is formed by adding a kinetic tunneling term to the interaction Hamiltonian of a classical spin glass.
  • D. Quantum Spin Glasses and Annealing: The location of quantum critical points guides kinetic-term selection and annealing paths intended to maintain a sizable gap.
  • D. Quantum Spin Glasses and Annealing: Quantum spin-glass transitions can be driven by thermal fluctuations, quantum fluctuations, or both.
  • D. Quantum Spin Glasses and Annealing: The transverse Ising spin-glass model is emphasized because its quantum fluctuations can be adjusted and then reduced during annealing.
  • D. Quantum Spin Glasses and Annealing: Tuning the tunneling field may be faster than tuning temperature for reaching the glass phase, according to the reviewed results.
  • D. Quantum Spin Glasses and Annealing: In LiHo0.167Y0.833F4, increasing transverse field lowers the glass transition temperature and improves ergodicity near ground states through tunneling-induced overlap.
  • D. Quantum Spin Glasses and Annealing: Replica-symmetry restoration by quantum fluctuations remained unsettled, although slow tunneling-field withdrawal could bring systems near the classical ground state.

III. QUANTUM ANNEALING

Quantum annealing replaces thermal fluctuations with controllable quantum fluctuations to navigate rugged optimization landscapes. By slowly reducing the quantum term, adiabatic evolution can lead toward the classical problem’s ground state, subject to spectral-gap conditions.

  • III. QUANTUM ANNEALING: Thermal annealing can become ineffective because rugged landscapes contain high barriers, many trapping minima, and exponentially many configurations.For n Ising spins, the configuration count is roughly 2^n; barriers may scale with system size in infinite-range problems.
  • III. QUANTUM ANNEALING: Quantum tunneling can cross sufficiently narrow barriers and may produce faster relaxation than thermal annealing in glassy systems.The paper reviews quantum annealing as a way to address ergodicity problems caused by trapping in local minima.
  • III. QUANTUM ANNEALING: A double-well example illustrates annealing from a delocalized state toward a deeper, narrower minimum as kinetic energy decreases.At high kinetic energy the ground state spreads across both wells; as kinetic energy is reduced, the potential term favors the deeper minimum.
  • III. QUANTUM ANNEALING: Quantum annealing adds a non-commuting kinetic term Γ(t)Hkin to the classical Hamiltonian HC, with Γ controlling quantum fluctuations.The total Hamiltonian’s ground state is generally a superposition of classical Hamiltonian eigenstates.
  • III. QUANTUM ANNEALING: Starting from a high-Γ uniform superposition and reducing Γ slowly can preserve the instantaneous ground state until the Hamiltonian becomes classical.This conclusion assumes sufficiently slow evolution and no problematic ground-state level crossing.
  • III. QUANTUM ANNEALING: The adiabatic guarantee depends on the instantaneous gap, which may vanish at a phase boundary for infinite systems but is unlikely to vanish in finite random samples.The paper therefore distinguishes the infinite-system limitation from the possibility of successful finite-sample annealing.

A. Quantum Monte Carlo Annealing

Quantum Monte Carlo annealing replaces real-time quantum evolution with Monte Carlo sampling of quantum systems. Path Integral Monte Carlo is most commonly used because its implementation is simpler, while alternative zero-temperature methods have practical drawbacks.

  • A. Quantum Monte Carlo Annealing: Quantum Monte Carlo annealing may use either finite-temperature or zero-temperature algorithms, with finite-temperature PIMC used most often.The paper attributes PIMC’s prevalence partly to its simpler implementation.
  • A. Quantum Monte Carlo Annealing: Zero-temperature transfer-matrix and Green’s function Monte Carlo are alternatives, but their drawbacks make them slower than PIMC in practice.The paper presents this as a practical comparison among Monte Carlo annealing methods.
  • A. Quantum Monte Carlo Annealing: Green’s function Monte Carlo often requires guidance based on prior knowledge of the wave function and may fail without it.Such prior knowledge is described as unlikely for random optimization problems, restricting the method’s scope.
  • A. Quantum Monte Carlo Annealing: Transfer-matrix Monte Carlo samples the instantaneous Hamiltonian’s ground state through a projective method and a higher-dimensional classical-system representation.The Hamiltonian is transformed into a suitable positive matrix interpreted as a transfer matrix.
  • A. Quantum Monte Carlo Annealing: PIMC maps a d-dimensional quantum Hamiltonian to an effective classical Hamiltonian in (d + 1) dimensions using Suzuki-Trotter formalism.Annealing then simulates the mapped classical system at fixed low temperature while reducing quantum fluctuations.

1. A Short-Range Spin Glass

Quantum annealing can accelerate relaxation in some rugged optimization landscapes, including short-range spin glasses and random TSP instances, but its performance depends strongly on the problem and algorithmic choices.

  • A Short-Range Spin Glass: For an 80 × 80 lattice, PIMC-QA preserves logarithmic residual-energy relaxation but achieves ζ = 6, exceeding the classical bound ζ ≤2.The reported asymptotic comparison reaches a fixed residual energy in one day of CPU time with PIMC-QA versus about 30 years with CA.
  • A Short-Range Spin Glass: Landau-Zener cascade arguments attribute the faster annealing trend to residual energy scaling as ǫres ∼(log τ)−ζQ, with ζQ potentially as high as 6.The argument treats multiple small-gap crossings as a cascade of independent tunneling events.
  • The Traveling Salesman Problem: For random-metric TSP, PIMC finds approximately minimal tours more efficiently than CA, using constrained moves that preserve valid tours.The classical implementation restricts Monte Carlo updates to 2-opt moves; the quantum case requires a transverse field enforcing the tour constraints.
  • The Traveling Salesman Problem: The TSP residual-path-length relaxation resembles that of the two-dimensional EA glass, indicating a spin-glass-like potential-energy landscape for random TSP.The paper states that this similarity supports applying the Landau-Zener tunneling picture to TSP, while expecting little improvement from real-time Schrödinger dynamics over Monte Carlo methods.
  • A Short-Range Spin Glass: PIMC-QA can underperform CA: for random 3-SAT with a linear Γ schedule, it gives much worse results, while both methods trail WALKSAT.For image restoration, PIMC-QA performs exactly like CA, showing that the advantage is problem-dependent.
  • A Short-Range Spin Glass: PIMC-QA performance depends on the kinetic term, constraint-handling moves, finite temperature, and the availability of sufficiently good approximate solutions or landscape gradients.The paper notes that arbitrary kinetic terms complicate Suzuki-Trotter mappings and that Monte Carlo methods perform worse when good solutions are sparse and no overall gradient guides the search.

3. Random Field Ising Model: How a Choice of Kinetic Term Improves Annealing Results

In the random-field Ising model, quantum annealing performance improves when a ferromagnetic transverse interaction is added to the conventional single-spin-flip term. The improvement is linked to enlarging the ground-to-first-excited-state gap.

  • Random Field Ising Model: How a Choice of Kinetic Term Improves Annealing Results: Quantum annealing permits multiple kinetic-term choices, allowing annealing paths designed to avoid regions where the energy gap becomes very small.The paper connects this flexibility to knowledge of the phase diagram, especially the location of the quantum critical point.
  • Random Field Ising Model: How a Choice of Kinetic Term Improves Annealing Results: Quantum annealing is unsatisfactory when the interaction strength J is much larger than the random-field scale hz.
  • Random Field Ising Model: How a Choice of Kinetic Term Improves Annealing Results: Adding a ferromagnetic transverse term to the random-field Ising Hamiltonian improves quantum-annealing results considerably.Exact diagonalization indicates that the added term increases the ground-to-first-excited-state gap and decreases the characteristic timescale.

B. Quantum Annealing Using Real-time Adiabatic Evolution

Real-time adiabatic quantum annealing applies quantum evolution to optimization and search, with performance governed by the kinetic term, energy gap, and landscape barriers. The reviewed results show quantum advantages for narrow barriers and selected scaling regimes, while some problems retain limited or uncertain asymptotic benefits.

  • Search problems: Grover-type spatial search achieves O(√N) scaling for dimensions d ≥4, with no further improvement reported.The kinetic term is represented by lattice hopping, and the speed-up occurs near the critical kinetic-term value.
  • Constraint-satisfaction problems: For the NP-complete clause-satisfaction model, smooth quadratic runtime scaling was observed only for l ≤20 and did not establish asymptotic quadratic behavior.The construction uses a clause-violation Hamiltonian, a single-bit-flip kinetic term, and an equal-superposition initial ground state.
  • Barrier structure: For spiky barriers, quantum annealing can outperform thermal annealing because tunneling penetrates barriers that are high but narrow.The review contrasts this with finite-ranged systems, where the two annealing methods may have similar efficiency.
  • Scaling behavior: A well depth χ ∼ αN yields evolution time independent of N, whereas χ ∼ N^γ with γ > 1 loses the speed-up through non-adiabaticity.The N-independent runtime is associated with an O(1) overlap of the final ground state with the target state.
  • Scaling behavior: The final success probability depends non-monotonically on the final Γ: values that are too small slow relaxation, while values that are too large delocalize the ground state.Numerical verification uses τmin, the minimum time required to reach P(|w⟩) = 0.33, across different N.

C. Annealing of a Kinetically Constrained System

The review examines quantum annealing in kinetically constrained systems, where dynamics are slow because constraints create effectively infinite barriers despite trivial ground states. Quantum fluctuations provide barrier-crossing pathways, and the reported comparison shows substantially faster quantum relaxation than classical annealing in the studied chain.

  • Kinetically constrained systems: Kinetically constrained systems have trivial ground-state structure but complex relaxation caused by explicit dynamical constraints.These models isolate the contribution of constrained dynamics from complexity caused by the energy landscape.
  • Model construction: In the generalized double-well model, a neighboring particle’s state determines whether the next well has a barrier of height χ and width a.The barrier appears when the preceding particle occupies its lower well and disappears when it occupies its upper well.
  • Quantum dynamics: Quantum fluctuations give finite tunneling probabilities for crossing the constrained double-well barriers.The tunneling description uses a semiclassical scattering picture for a particle with kinetic-energy expectation Γ.
  • Quantum–classical comparison: Quantum annealing reaches final order mf ∼0.92 in about 10^4 steps, compared with about 10^7 steps for classical annealing.The comparison uses the same disordered initial configuration and starts from Γ0 = T0 = 100, with τQ = 1.8 × 10^2 and τC = 10^6.

D. Experimental Realization of Quantum Annealing

Experiments in LiHo0.44Y0.56F4 compare thermal and quantum relaxation paths through the temperature–transverse-field phase diagram. The quantum path includes a low-temperature, high-field segment and is often associated with faster relaxation at sufficiently low temperature.

  • Classical path: Along the classical path A→B→C, the transverse field remains zero until the final temperature, so relaxation is thermal.The path is represented by the dashed arrow in the phase diagram.
  • Quantum path: Along the quantum path A→D→C, high transverse field is applied while temperature is low enough for fluctuations to be mainly quantum mechanical.The transverse field is lowered only after the system reaches the final temperature.
  • Observed relaxation: Quantum-path relaxation is often much faster than classical-path relaxation at sufficiently low temperature.The material’s phase diagram identifies a ferromagnetic region FM and a slowly relaxing glassy domain-wall region G.
  • Experimental protocol: The experiment compares classical and quantum cooling paths from a high-temperature paramagnet to a low-temperature glassy phase.Both paths are followed in the Γ–T plane, with relaxation spectroscopy performed during cooling.

IV. CONVERGENCE OF QUANTUM ANNEALING ALGORITHMS

The review compares convergence behavior in quantum annealing, emphasizing power-law transverse-field schedules for TIM systems and their similarity across simulation dynamics. It also places quantum annealing within analog computation and quantum-quenching approaches.

  • Convergence bounds: Quantum annealing requires only power-law decay of the transverse field for TIM convergence, unlike classical annealing’s inverse-logarithmic temperature decay.The convergence advantage does not change NP-complete complexity because the convergence time remains exponential in N.
  • Convergence bounds: The power-law annealing bound is similar for path-integral Monte Carlo and real-time Schrödinger evolution despite their different dynamics.For real-time evolution, the parameter ξ is exponentially small in N for large N.
  • Analog quantum computation: Annealing toward the ground state in the classical limit provides an analog quantum-computation framework for hard optimization problems.The review presents this framework through mappings to classical spin glasses, quantum spin glasses, and subsequent annealing.

VII. APPENDIX

The appendix derives the classical representation of a transverse-Ising model using the Suzuki–Trotter decomposition. The resulting system has an additional Trotter direction and becomes a (d+1)-dimensional classical spin system as temperature approaches zero.

  • Suzuki–Trotter construction: The transverse-Ising-model partition function is transformed using the Trotter formula even when the component operators do not commute.The decomposition introduces M replicated factors in the partition function.
  • Suzuki–Trotter construction: The replicated configurations sum over all possible whole-system spin configurations, with periodic boundary conditions in the Trotter direction.The boundary condition is S_N+1,p = S_1,p.
  • Effective classical model: The effective classical Hamiltonian is equivalent to the original quantum Hamiltonian after introducing M Trotter replicas.For meaningful comparison, M is of order 1/T when ℏ = 1.
  • Effective classical model: As T approaches zero, M approaches infinity and the effective Hamiltonian describes spins on a (d+1)-dimensional lattice.The extra dimension arises from the additional replica label k for each spin variable.

2. Quantum Quenching of a Long Range TIM

The long-range transverse-Ising model is analyzed after a quench across its quantum critical point. Its infinite-range structure makes mean-field dynamics exact and permits a classical angular-momentum description.

  • Model and critical point: For the infinite-range model, mean-field theory is exact and yields a quantum critical point Γc = J/2.The order parameter satisfies m = 0 for Γ > Γc and m ≠ 0 for Γ < Γc.
  • Model and critical point: The Hamiltonian is written as H = h·S_tot with h = Jm ẑ − Γ x̂, linking the collective spin to an effective field.The total spin is represented using polar components, enabling classical equations of motion.
  • Quench dynamics: The collective-spin dynamics obey dS/dT = S × h for the z and x components.This equation provides the dynamical starting point for the post-quench analysis.
  • Quench dynamics: A quench from Γi > Γc to Γf < Γc is used to study the resulting ordered dynamics.The system has S = N/2, and the final field is chosen below the critical point.
  • Quench dynamics: The quench analysis identifies Γf through energy comparison between states with and without order.The resulting condition is expressed in terms of J and the final transverse field.
Loading 0801.2193v3…