Prospects for Quantum Enhancement with Diabatic Quantum Annealing

E. J. Crosson; D. A. Lidar

Source-linked AI summary

Prospects for Quantum Enhancement with Diabatic Quantum Annealing

E. J. Crosson, D. A. Lidar

arXiv:2008.09913v1Aug 22, 2020quant-phcond-mat.supr-con

TL;DR

The paper asks whether quantum annealing can achieve speedups in combinatorial optimization and related sampling despite limited empirical evidence. It evaluates continuous-time Hamiltonian protocols, especially diabatic quantum annealing, and argues that improved coherence and control justify intermediate-scale exploration. The central conclusion is that coherent diabatic dynamics, alongside reverse annealing and quantum walks, offer the most promising routes within the QA framework.

Problem
The paper addresses the absence of unequivocal quantum speedup evidence for QA in heuristic optimization and clear advantage in excited-state sampling.
Method
It evaluates time-dependent transverse-field Ising Hamiltonian protocols that extend traditional ground-state QA with more advanced continuous-time controls.
Results
The paper argues that coherent diabatic quantum annealing, reverse annealing, and continuous-time quantum walks are promising candidates for quantum enhancement.
Takeaways & Limitations
These protocols merit intermediate-scale hardware investigation because most lack known, or likely to be discovered, efficient classical simulations and show limited early evidence for speedups.

Abstract

from arXiv · show

We assess the prospects for algorithms within the general framework of quantum annealing (QA) to achieve a quantum speedup relative to classical state of the art methods in combinatorial optimization and related sampling tasks. We argue for continued exploration and interest in the QA framework on the basis that improved coherence times and control capabilities will enable the near-term exploration of several heuristic quantum optimization algorithms that have been introduced in the literature. These continuous-time Hamiltonian computation algorithms rely on control protocols that are more advanced than those in traditional ground-state QA, while still being considerably simpler than those used in gate-model implementations. The inclusion of coherent diabatic transitions to excited states results in a generalization called diabatic quantum annealing (DQA), which we argue for as the most promising route to quantum enhancement within this framework. Other promising variants of traditional QA include reverse annealing and continuous-time quantum walks, as well as analog analogues of parameterized quantum circuit ansatzes for machine learning. Most of these algorithms have no known (or likely to be discovered) efficient classical simulations, and in many cases have promising (but limited) early signs for the possibility of quantum speedups, making them worthy of further investigation with quantum hardware in the intermediate-scale regime. We argue that all of these protocols can be explored in a state-of-the-art manner by embracing the full range of novel out-of-equilibrium quantum dynamics generated by time-dependent effective transverse-field Ising Hamiltonians that can be natively implemented by, e.g., inductively-coupled flux qubits, both existing and projected at application scale.

I. INTRODUCTION

The paper reevaluates quantum annealing as evidence for quantum enhancement remains inconclusive, focusing on time-dependent transverse-field Ising dynamics and diabatic transitions beyond traditional ground-state evolution.

Motivation: Quantum annealing seeks low-energy solutions of classical Ising optimization problems using quantum fluctuations as an alternative to classical thermal fluctuations.Its physical implementation is motivated by the possibility of speedups over classical hardware.
Motivation: The paper reevaluates QA because prior experiments have not established an unequivocal quantum speedup in heuristic optimization or clear advantage for excited-state sampling.The authors undertake a theoretical reassessment of promising directions for the field.
Model: The framework studies time-dependent transverse-field Ising Hamiltonians, with controllable transverse and longitudinal fields and couplings subject to experimental constraints.The schedule is defined by the time dependence of A(t) and B(t), while implementation precision limits the realized parameters.
Practical scope: The model is simpler to control than typical gate-based optimization Hamiltonians but lacks modularity, complicating calibration and error correction.The paper notes that no fault-tolerance proof currently exists for this computational model, and physical leakage states must also be addressed.
Model: Diabatic quantum annealing permits transitions to and from low-energy excited states when evolution does not follow instantaneous energy eigenstates.This generalizes the adiabatic QA setting while retaining continuous-time Hamiltonian evolution.

B. Diabatic Quantum Annealing (DQA)

DQA extends adiabatic computation from a single instantaneous eigenstate to a narrow low-energy subspace, allowing controlled diabatic transitions while remaining separated from higher-energy states by a gap.

Definition: DQA relaxes adiabatic evolution by keeping the system within a narrow, contiguous energy band rather than a single instantaneous eigenstate.The band has width δ, and DQA concerns optimization while DQC is the corresponding universal computational model.
Implications: DQA final states need not approximate problem-Hamiltonian ground states, and its dynamics are generically non-local for all T>0.Digitizing the resulting unitary on gate-model hardware requires Ω(nT) gates for accurate approximation.
Subspace preservation: A low-energy subspace C can remain approximately preserved when separated from the rest of the spectrum by a gap ∆(s).The generalized adiabatic theorem bounds leakage from C by a quantity scaling as ξ(s)/T under the stated regularity conditions.
Definition: The energy width δ distinguishes DQA from QA: QA keeps δ(s)=0, whereas DQA permits δ(s)>0 while preserving a low-energy subspace.The paper additionally imposes δ(s)=O(1) to distinguish DQA from gate-model evolution with extensively growing energy width.
Implications: The same theorem controlling ground-subspace leakage also supports preservation of broader low-energy subspaces, so DQA is not intrinsically harder to impose than QA.The relevant bounds depend on the chosen subspace C and its dimension and spectral separation.

C. Structure of the remainder of this Perspective

The paper surveys optimization protocols, classical simulation barriers, nonstoquasticity, complexity arguments, and noise before advocating intermediate-scale QA hardware and error suppression.

Scope: The optimization discussion evaluates coherent and weakly-decoherent QA and DQA protocols according to evidence for speedups and expected classical simulation overhead.The authors seek cases where classical simulation is plausibly intractable.
Scope: The paper treats nonstoquastic interactions as desirable but not essential for quantum enhancement.It contrasts their sign-problem benefits with stoquastic out-of-equilibrium DQA, which can also support classical intractability.
Scope: Formal complexity arguments are examined critically because classical intractability in sampling does not automatically establish practical enhancement on real devices.The paper explicitly distinguishes these two concepts.
Noise: Intrinsic control errors of a few percent can drive fidelity with an intended approximately thermal output distribution nearly to zero above several hundred qubits.At application scale around n∼10000 logical qubits, the authors state that error suppression or fault tolerance would be required if such errors cannot be reduced.
Conclusion: The paper advocates QA hardware primarily for algorithmic exploration at the hundreds-of-qubits scale and secondarily for developing Hamiltonian error suppression.This approach aims to increase solvable optimization scale without requiring the full overhead of fault tolerance.

III. OPTIMIZATION USING TRANSVERSE-FIELD HAMILTONIAN INTERPOLATION

The paper classifies transverse-field interpolation by annealing direction and coherence, identifying coherent or C-coherent diabatic evolution as the most promising forward-annealing regime while excluding strongly decoherent dynamics.

Forward QA: Forward QA uses monotonically decreasing A(t) and increasing B(t), with the problem Hamiltonian encoding the optimization solution in its ground state.The resulting transverse-field interpolation is stoquastic.
Classification: Diabatic TF-HI preserves a low-energy subspace C, whereas adiabatic TF-HI follows the ground state with δ=0.The distinction concerns the allowed energy width during evolution.
Coherence: The framework distinguishes fully coherent, weakly-decoherent, and strongly-decoherent dynamics according to which coherences persist over the evolution time T.Weakly-decoherent dynamics preserve coherence within energy eigenstates but not necessarily between different eigenstates.
Prospects: For forward annealing, coherent and C-coherent diabatic evolution is judged most promising because no reasonably competitive classical algorithm is known for it.The reverse-annealing cases are described as more encouraging overall, with weakly-decoherent adiabatic reverse annealing identified as the only unpromising case.
Coherence: Strong decoherence destroys coherence between computational-basis states on timescales shorter than T, leaving little prospect for a meaningful quantum algorithm.The paper therefore does not pursue this limit further.
Coherence: C-coherence preserves coherent superpositions of energy eigenstates inside a low-energy subspace C while allowing decoherence involving states outside C.When C is the ground subspace it reduces to the weakly-decoherent case; when C is the full Hilbert space it becomes fully coherent.

C. Four forward annealing cases

The four forward annealing cases differ by coherence and diabaticity, with current evidence most unfavorable for weakly-decoherent diabatic TF-HI but leaving control-noise effects unresolved.

Forward annealing uses monotonically decreasing A(t) and increasing B(t).
Coherent adiabatic TF-HI: Coherent adiabatic TF-HI is governed by the minimum spectral gap and has mixed evidence, including a tuned quadratic Grover speedup and efficient QMC simulations for some cases.
Weakly-decoherent adiabatic TF-HI: Weakly-decoherent adiabatic TF-HI remains close to the instantaneous thermal state and inherits a similar complexity-theoretic limitation.
Weakly-decoherent diabatic TF-HI: Weakly-decoherent diabatic TF-HI has shown scaling over simulated annealing but no scaling advantage over state-of-the-art classical methods for relevant optimization problems.
Weakly-decoherent diabatic TF-HI: The negative assessment may reflect significant control noise in current devices rather than the regime’s intrinsic computational power.

4. Coherent and C-coherent Forward Diabatic TF-HI

Coherent diabatic TF-HI is presented as the most promising forward-annealing variant because its nonequilibrium dynamics resist known efficient classical simulation and can exploit diabatic excitation and de-excitation.

The paper identifies fully coherent and C-coherent diabatic TF-HI as its most promising algorithmic variants.
No efficient classical simulation is known for coherent diabatic transverse-field dynamics, unlike equilibrium stoquastic cases amenable to QMC or SVMC in practice.
Universal-control protocols are not proposed for implementation because their substantial overheads make them relatively impractical.
For MAX-2-SAT at n = 20 qubits, hard instances had optimal annealing times orders of magnitude below the adiabatic timescale, with early excitation later returning amplitude to the ground state.
Initializing the transverse-field first excited state similarly improved residual energy at fixed anneal time because late avoided crossings enabled diabatic de-excitation.
C-coherent diabatic TF-HI solves the symmetric Hamming-weight-with-a-spike problem in O(1) time through a diabatic cascade, although symmetry contributes substantially.
The paper therefore regards coherent and C-coherent diabatic TF-HI as promising quantum-advantage candidates.
Additional-control protocols broaden the search for speedup but introduce parameter-selection costs that can, in extreme cases, inherit the original problem’s NP-hard complexity.

A. Reverse Annealing

Reverse annealing extends QA with evolutions that incorporate an off-diagonal Hamiltonian and can exploit diabatic or thermal behavior. The reviewed examples include a provable exponential speedup for glued trees, but rely on demanding state-preparation or oracle assumptions.

Provable exponential speedup: Glued-trees reverse annealing achieves a provable exponential speedup using a stoquastic Hamiltonian with essential ground-to-first-excited-state diabatic transitions.The speedup requires coherence only within the subspace of the two lowest energy eigenstates.
Provable exponential speedup: The glued-trees problem is contrived, sensitive to control noise, and requires oracle access to the graph description.
Weakly-decoherent setting: Efficient preparation of the instantaneous thermal state would also solve the glued-trees problem in a weakly-decoherent setting.Outside intervals where the gap is exponentially small, the thermal state can be arbitrarily close to the ground state; within them, it contains a nearly uniform ground/first-excited-state mixture.
Weakly-decoherent setting: The thermal-state argument depends on guaranteeing efficient and accurate preparation of ρβ(s) throughout the anneal.

2. Coherent adiabatic reverse annealing

Coherent adiabatic reverse annealing uses an additional diagonal initialization Hamiltonian and a controlled path to alter the phase-transition structure. Theory indicates substantial speedups in oracle and p-spin settings, but practical generality and local analog implementability remain constrained.

2. Coherent adiabatic reverse annealing: A Hamiltonian-oracle construction provides a provable superpolynomial speedup for determining whether a graph contains a large cycle from local oracle queries.The quantum algorithm runs in polynomial time, while classical algorithms require n^Ω(log(n)) queries.
2. Coherent adiabatic reverse annealing: The oracle construction is unsuitable for analog implementation with a local Hamiltonian because it requires many-body interactions.It is suitable for gate-model Hamiltonian simulation, but the paper therefore treats its quantum-advantage implications cautiously.
2. Coherent adiabatic reverse annealing: First-order quantum phase transitions can produce exponentially small gaps and exponentially long adiabatic evolutions, motivating reverse annealing as a way to soften this obstruction.
2. Coherent adiabatic reverse annealing: ARA initializes a chosen classical state through Hinit and uses λ(t) and C(t) to concatenate a reverse evolution with the annealing path.Hinit is diagonal in the computational basis, while A(t) and C(t) decrease and B(t) increases over the evolution.
2. Coherent adiabatic reverse annealing: Reverse annealing can turn the p-spin model’s first-order transition into a second-order transition with a polynomially small gap.This is achieved by choosing an appropriate path in the (λ, C) plane.
2. Coherent adiabatic reverse annealing: The oracle-based ARA result embeds knowledge about the classical solution in Hinit, leaving its generalization to hard optimization problems unclear.

3. Iterated coherent and weakly-decoherent reverse annealing

Iterated reverse annealing uses prior states and diabatic transitions to search for lower-energy configurations, with performance depending strongly on protocol design, decoherence, and the transverse-field scale.

Iterated coherent reverse annealing: Sombrero-AQC iteratively feeds a trial state into a new annealing run, using intermediate delocalization to enable tunneling toward another local minimum.The initial Hamiltonian is reprogrammed from the previous classical state.
Iterated coherent reverse annealing: Numerical simulations found improved performance over forward TF-HI for quantum parallel tempering, quantum population annealing, and a quantum-assisted genetic algorithm.The genetic algorithm treats reverse evolution as mutation while recombination and selection remain classical.
Fixed diagonal Hamiltonian: The fixed-diagonal-Hamiltonian protocol failed to converge to the p-spin ground state because iteration did not shift final-state probabilities toward lower energies.The required energy-shifting condition was violated in the p-spin model.
Weakly-decoherent reverse annealing: Weak decoherence enabled relaxation to the p-spin ground state, increasing success probabilities when the inversion point was near or before the avoided crossing.The mechanism was dephasing in the instantaneous energy eigenbasis and associated thermal relaxation.
D-Wave implementation: Reverse-annealing dynamics remain frozen below a threshold transverse field, so Amax must be large enough for quantum fluctuations to explore the Hilbert space.A mid-anneal pause near the minimum gap improved success probability under conditions preserving memory of the initial state.
Conclusion: The authors regard reverse-annealing heuristics as promising because they explicitly exploit diabatic transitions, despite limited rigorous understanding.Iterated reverse annealing has also been used in D-Wave quantum simulations of topological phases.

B. Quantum Walks on a Boolean Hypercube with a Rapid Quench

Quantum-walk and QAOA-related protocols connect rapid-quench Hamiltonian evolution with optimized diabatic annealing, while evidence for speedup remains mixed and problem-dependent.

Quantum walks: A Boolean-hypercube quantum walk uses a time-independent Hamiltonian H = γL + HC, with γ tuned to maximize ground-state probability after evolution for time T.The protocol requires an instantaneous quench and then keeps the Hamiltonian on.
Quantum walks: The SK result suggested a super-quadratic speedup over brute-force search, but lacked a theoretical guarantee and may reflect finite-size effects.The tested systems had at most 11 qubits.
Connection to QAOA: Quantum-walk results are interpreted as coherent diabatic forward annealing, linking their initial quench to optimized QAOA schedules.An analytical MAX-K-LIN-2 treatment also identified energy conservation as a route to solutions below random-guess energy.
QAOA comparison: QAOA and coherent diabatic TF-HI have comparable positive and negative evidence for limited speedups relative to specific classical algorithms.QAOA also faces finite-depth negative results, local-algorithm limitations, and reachability deficits.
QAOA comparison: Optimal QAOA angles appear to digitize a smooth curve, corresponding to a Trotterized continuous-time transverse-field Ising evolution.Optimal-control simulations commonly favored bang-anneal-bang protocols over purely QAOA or purely adiabatic schedules.

V. THE ROLE OF NONSTOQUASTICITY IN CLASSICAL INTRACTABILITY

Nonstoquasticity is associated with classical simulation challenges, but its algorithmic value is unsettled and may require substantial implementation overhead or fail to improve intermediate-scale performance.

Classical intractability: Nonstoquastic Hamiltonians create a QMC sign problem and can produce classically intractable measurement distributions, while out-of-equilibrium DQA can do so comparably.The paper separates this classical intractability from claims of algorithmic enhancement.
Classical simulation: Finding a basis that reveals stoquasticity can itself be NP-hard, and Markov-chain equilibration can dominate simulation runtime for transverse-Ising spin glasses.Thus apparent stoquasticity does not automatically imply efficient classical simulation.
Hardware implications: Arbitrary 2-local interactions could emulate broader stoquastic and nonstoquastic Hamiltonians, supporting Hamiltonian error suppression and more general diabatic interpolation.The authors state that these potential avenues do not specifically require +XX rather than −XX interactions.
Scope limitation: Strong multi-spin fluctuations have no provable equilibrium advantage in classical simulatability and may resemble multi-bit proposals in classical simulated annealing.The paper cautions that any benefit could disappear at intermediate scale.
Limitations: Formal evidence for nonstoquastic sampling hardness relies on universal constructions with qubit, gadget, and coupling-control overhead, so broader claims rest mainly on practical evidence.The practical evidence includes the QMC sign problem and the absence of other known efficient samplers.
Ground-state optimization: Nonstoquastic Hamiltonians can sometimes change first-order transitions into second-order transitions, replacing exponentially small gaps with polynomially small ones.This improvement is case-specific, and multimodal ground-state distributions still inevitably produce small gaps.

VI. SAMPLING APPLICATIONS AND MACHINE LEARNING

The paper distinguishes classical intractability of quantum sampling from useful enhancement, emphasizing that hardness arguments depend on strong assumptions and do not by themselves establish practical advantage.

Sampling and enhancement: Classical intractability of a quantum process does not imply that the process provides computational enhancement.The paper applies this distinction especially to quantum-sampling claims.
Hardness arguments: Hardness arguments commonly use postselection to connect efficient classical simulation with an implausible collapse of classical and quantum complexity classes.The argument proceeds through postselected universality and hypothetical classical simulation.
Hardness arguments: These arguments require exponentially small trace-norm error in their basic form, making the precision requirement unrealistic and worst-case in character.Constant-error variants require additional ensemble assumptions.
Architectural scope: Two-dimensional constant-depth circuits have efficient classical sampling simulations, whereas unrestricted connectivities are still expected to support the formal hardness arguments.The contrast is attributed to low entanglement width in constant-depth circuits.
Sampling and enhancement: Hardness of sampling is necessary but insufficient for enhancement, as illustrated by earlier IQP and linear-optics proposals and by NISQ optimization claims.The paper argues that the usefulness of output distributions must be examined directly.
Classical simulation: If an efficiently computable unnormalized density w existed for a quantum output distribution, classical MCMC could be used to sample it.This frames the issue as whether classical difficulty reflects the distribution itself or the absence of a concise density description.

B. Machine Learning

The paper presents quantum machine learning models based on quantum dynamics and sampling, emphasizing DQA as the setting needed for classical simulation hardness. It also describes DQA analogues of parameterized quantum-circuit models while noting that quantum learning supremacy remains unresolved.

Quantum machine learning relies on quantum dynamics, making its training process difficult to simulate classically in general.
Quantum Boltzmann Machines sample thermal equilibrium states of quantum Hamiltonians, while Born machines use measurement distributions from non-thermal quantum states.
A DQA-IBM replaces a parameterized quantum circuit with a smooth, finite-parameter annealing schedule and can use existing classical parameter-training methods.
Quantum Circuit Ising Born Machines cannot be efficiently classically simulated in the worst case, and the same is asserted for DQA-IBMs.
Whether these models learn distributions more efficiently than every classical algorithm remains an open question.

B. Hamiltonian Error Suppression

The paper examines Hamiltonian error suppression and related continuous-time protocols as ways to protect diabatic quantum annealing while avoiding the full resource demands of gate-model fault tolerance. It identifies coherent or C-coherent diabatic dynamics as the most promising forward-annealing regime, while emphasizing unresolved protection and implementation questions.

Hamiltonian Error Suppression: Standard gate-model fault tolerance relies on growing code families, fast measurements, and substantial classical decoding overhead.
Hamiltonian Error Suppression: Hamiltonian Error Suppression instead uses error-detecting codes without intermediate measurements or classical processing for continuous-time computation.
Hamiltonian Error Suppression: Logarithmically growing energy-penalty strength can exponentially suppress Markovian-environment errors at fixed temperature when the spectral gap closes no faster than inverse polynomially.
Hamiltonian Error Suppression: Open questions concern exponentially closing gaps, fully two-local exponential suppression, and stronger protection against intrinsic analog control errors.
Diabatic quantum annealing: The paper distinguishes four coherence and diabaticity regimes, identifying coherent or C-coherent diabatic forward annealing as the most promising case.
Diabatic quantum annealing: Diabaticity can arise from an evolution time shorter than the energy-gap timescale, without requiring pulsed interactions.
Hamiltonian Error Suppression: Nonstoquastic Hamiltonians support architectures for universal adiabatic or Hamiltonian computation with error suppression, while reverse annealing offers a stoquastic alternative for avoiding some first-order transitions.
Machine learning: Sampling applications such as Ising Born machines benefit from being formulated in the DQA setting when classical hardness results apply.