Adiabatic quantum computing is a powerful framework for state preparation, while its evolution time often scales quadratically in the inverse Hamiltonian spectral gap, leading to sub-optimal computational complexity. In this work, we introduce a nonlinear adaptive strategy for finding the time scheduling function, and show that the gap dependence can be quadratically improved to be inverse linear for a wide range of systems under a mild gap measure condition. Through variational analysis, we further demonstrate the optimality of our schedule for systems with linear gap and the partial optimality for general systems, while we also rigorously show that the commonly used linear schedule is never optimal.
Adiabatic quantum computing is a powerful framework for state preparation, while its evolution time often scales quadratically in the inverse Hamiltonian spectral gap, leading to sub-optimal computational complexity. In this work, we introduce a nonlinear adaptive strategy for finding the time scheduling function, and show that the gap dependence can be quadratically improved to be inverse linear for a wide range of systems under a mild gap measure condition. Through variational analysis, we further demonstrate the optimality of our schedule for systems with linear gap and the partial optimality for general systems, while we also rigorously show that the commonly used linear schedule is never optimal.
The efficiency of adiabatic quantum evolution is governed by the evolution time T , which typically scales as O ( Δ − 2 ) with the minimum energy gap Δ . However, the rigorous lower bound is O ( L Δ − 1 ) , where L is the adiabatic path length. Although L is formally upper bounded by O ( Δ − 1 ) , such a bound is often too loose in practice, and L can be bounded independently of Δ . This indicates the potential for a quadratic speedup through adiabatic schedule construction. Here, we introduce the constant geometric speed (CGS) schedule, which traverses the adiabatic path at a uniform rate. We show that this approach reduces the scaling of the evolution time by a factor of Δ − 1 , provided L remains bounded independently of Δ . We propose a segmented CGS protocol where path segment lengths are computed from eigenstate overlaps on the fly, reducing the prior spectral-knowledge requirement from the full gap function Δ ( s ) to just a global lower bound on the energy gap. Numerical tests on adiabatic unstructured search, N 2 , and a [2Fe-2S] cluster demonstrate the optimal Δ − 1 scaling, confirming a quadratic speedup over the standard linear schedule.
We develop a discrete adiabatic framework for Gibbs-state preparation in classical and quantum optimisation algorithms. For finite time-inhomogeneous reversible Markov chains, we derive a tracking theorem that bounds the distance between the evolving distribution and the instantaneous stationary state. The bound combines contraction of accumulated error with the new error generated as the stationary distribution changes. For Gibbs paths, it yields explicit step-complexity bounds and an effective tracking metric determined by the spectral gap and equilibrium energy fluctuations. The associated constant-speed schedule minimizes the metric-energy functional and, in the small-gap regime, takes the form β˙∝δ(β)/V(β), where V(β)=Varπβ(E). We then apply the discrete quantum adiabatic theorem to temperature-dependent Szegedy quantum walks, whose eigenphase gap satisfies Δw=Θ(δ+), with δ+ the underlying Markov kernel's right spectral gap. Under uniform bounds on the discrete operator variation and suitable spectral and path-integral assumptions, gap-adapted schedules give a sufficient fixed-accuracy cost of O(δ+,min−1/2). This gives a quadratic improvement in gap dependence relative to the classical inverse-gap relaxation scale under the stated assumptions. Numerical tests on a solvable two-state model and Sherrington-Kirkpatrick instances compare tracking and final preparation errors and investigate the transfer of schedules from smaller to larger systems.
A challenge with the Quantum Approximate Optimisation Algorithm (QAOA), and variational algorithms in general, is finding good variational parameters, a task which in itself can be NP-hard. Recent work has sought to de-variationalise QAOA by picking well-informed guesses for the variational parameters. The Linear Ramp QAOA (LR-QAOA) achieves this by using parameter schedules inspired by the quantum adiabatic algorithm. In this work, we propose Spectral Gap Informed Ramp QAOA (SGIR-QAOA), a new QAOA variant that incorporates spectral gap information from an adiabatic Hamiltonian, with the QAOA mixer Hamiltonian as the initial Hamiltonian, to construct smooth parameter schedules. SGIR-QAOA performs slow evolution where the spectral gap of the adiabatic Hamiltonian is small. We show that SGIR-QAOA has performance improvements over the LR-QAOA on Grover's problem at constant depth and that SGIR-QAOA requires shorter depths to achieve the same optimal solution probability. We then show that these performance benefits extend to a problem with potential practical applications - the Maximum Independent Set (MIS) problem. Finally, we demonstrate the scalability of the SGIR-QAOA method using extrapolated spectral gap information for scales that the spectral gap cannot be exactly evaluated, and show that the advantage appears to persist under mild depolarising noise.
Adiabatic quantum computation is a form of computation that acts by slowly interpolating a quantum system between an easy to prepare initial state and a final state that represents a solution to a given computational problem. The choice of the interpolation schedule is critical to the performance: if at a certain time point, the evolution is too rapid, the system has a high probability to transfer to a higher energy state, which does not represent a solution to the problem. On the other hand, an evolution that is too slow leads to a loss of computation time and increases the probability of failure due to decoherence. In this work, we train deep neural models to produce optimal schedules that are conditioned on the problem at hand. We consider two types of problem representation: the Hamiltonian form, and the Quadratic Unconstrained Binary Optimization (QUBO) form. A novel loss function that scores schedules according to their approximated success probability is introduced. We benchmark our approach on random QUBO problems, Grover search, 3-SAT, and MAX-CUT problems and show that our approach outperforms, by a sizable margin, the linear schedules as well as alternative approaches that were very recently proposed.
Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.
Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian.Such approaches have enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure.However, the most efficient of those procedures is still asymptotically suboptimal by a factor of log(κ).Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete-time evolutions.In combination with the qubitized quantum walk, our discrete adiabatic theorem gives a speed-up for all adiabatic algorithms.Here, we use this combination to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity.Our O[κ log(1/ )] complexity is also optimal in terms of the combined scaling in κ and the precision .Compared to existing suboptimal methods, our algorithm is simpler and easier to implement.Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.