Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06268

Adiabatic tracking and geometric schedules for classical and quantum Gibbs-state preparation

Pedro C. S. Costa, Mauro E. S. Morales, Dong An, Kaur Kristjuhan

quant-phmath-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations• Revised Oct 27, 2026 (v2)
v1 · Oct 5, 2026v2 · Oct 27, 2026
arXivHTMLPDF

Abstract

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 $\dotβ\proptoδ(β)/V(β)$, where $V(β)=\sqrt{\operatorname{Var}_{π_β}(E)}$. We then apply the discrete quantum adiabatic theorem to temperature-dependent Szegedy quantum walks, whose eigenphase gap satisfies $Δ_w=Θ(\sqrt{δ_+})$, 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.

Comments
55 pages, 12 figures

Related papers

Constant geometric speed schedule for adiabatic state preparation

Miao Han, Hyowon Park, Sangkook Choi

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.

arXiv:2510.01923•Physical Review Research•May 9, 2026•0 citations

Improved gap dependence in adiabatic state preparation by adaptive schedule

Xi Guo, Dong An

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.

quant-pharXiv:2512.10329•Dec 12, 2025•0 citations

From Heat to Homology: Spectral Gap Transfer for Exact Quantum Gibbs Sampling at All Temperatures

Caesnan M. G. Leditto, Kuo-Chin Chen, Min-Hsiu Hsieh

Preparing Gibbs states through dissipative dynamics requires controlling convergence for the chosen Hamiltonian $H$ and coupling operators. However, efficient implementation requires convergence guarantees from the spectral gap of the generator of the dynamics, which remains a crucial challenge. Recent results address the challenge by restricting the dynamics with structural assumptions about the Hamiltonian and its interactions. For the Chen-Kastoryano-Gilyen (CKG) construction and arbitrary finite-dimensional Hamiltonians, we prove an explicit comparison that converts a spectral gap estimate for the infinite-temperature generator into a lower bound on the spectral gap of the CKG quantum Gibbs sampler at every finite positive inverse temperature $β$. It allows a single spectral gap estimate at infinite temperature to certify convergence across Hamiltonians and temperatures. Such an estimate is often known from a classical spectral gap estimate, such as the classical random walk spectral gap. For Hodge Laplacians of simplicial complexes as Hamiltonians, we construct coupling operators whose generator at infinite temperature has the same spectral gap as a classical simplicial down-up walk. A positive spectral gap of the walk and bounded spectral width $W=λ_{\max}(H)-λ_{\min}(H)$ give a generator spectral gap independent of the number of simplices at every fixed temperature. We then establish conditions under which the sampler approximately prepares zero-energy (harmonic) states in polynomial evolution time. This provides a conditional convergence guarantee for the state preparation in the thermal approach to quantum topological data analysis.

quant-pharXiv:2610.02859•Oct 5, 2026•0 citations

Sequential quantum mixing for slowly evolving sequences of Markov chains.

Vedran Dunjko, Hans J. Briegel

In this work we consider the problem of preparation of the stationary distribution of irreducible, time-reversible Markov chains, which is a fundamental task in algorithmic Markov chain theory. For the classical setting, this task has a complexity lower bound of $\Omega(\delta^{-1})$, where $\delta$ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is $O(\sqrt{\delta^{-1}})$, with other dependencies contributing only logarithmically. However, this bound has only been achieved for a few special classes of Markov chains. In this work, we provide a method for the sequential preparation of stationary distributions for sequences of time-reversible $N$-state Markov chains, akin to the setting of simulated annealing methods. The complexity of preparation we achieve is $O(\sqrt{\delta^{-1}} \sqrt[4]{N})$, neglecting logarithmic factors. While this result falls short of the conjectured optimal time, it provides a quadratic improvement over na\{i}ve approaches. Moreover, for the case when the output distributions are required to be encoded in pure quantum states we identify the settings where our algorithm is strictly optimal. The settings of slowly evolving sequences of Markov chains naturally appear in reinforcement learning, and consequently our results can be readily applied in quantum machine learning as well.

•Mar 4, 2015•4 citations

Accelerating quantum Gibbs sampling without quantum walks

Jiaqi Leng, Jiaqing Jiang, Lin Lin

Szegedy's quantum walk quadratically accelerates reversible classical Markov chains, but extending this mechanism to efficiently implementable quantum Gibbs samplers has remained challenging beyond special classes. We present a walk-free quantum algorithm for preparing purified Gibbs states with a quadratic improvement in spectral-gap dependence for a broad class of quantum Gibbs samplers that satisfy exact Kubo-Martin-Schwinger detailed balance. Our main structural result is an explicit factorization of the corresponding parent Hamiltonian into noncommutative first-order operators. This turns purified Gibbs-state preparation into a singular-value filtering problem and enables a quantum singular value transformation algorithm with quadratically improved gap dependence under standard coherent-access and warm-start assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. Moreover, we construct noncommuting Hamiltonians with efficiently preparable warm starts whose refinement under quantum Gibbs samplers requires exponential time. For these models, our algorithm achieves an end-to-end quantum speedup over the worst-case mixing scale.

quant-pharXiv:2604.22996•Apr 28, 2026•0 citations

Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem

Pedro C. S. Costa, Dong An, Yuval R. Sanders +3 more

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.

arXiv:2111.08152•PRX Quantum•Oct 7, 2022•120 citations
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(β)\dotβ\proptoδ(β)/V(β)β˙​∝δ(β)/V(β), where V(β)=Var⁡πβ(E)V(β)=\sqrt{\operatorname{Var}_{π_β}(E)}V(β)=Varπβ​​(E)​. We then apply the discrete quantum adiabatic theorem to temperature-dependent Szegedy quantum walks, whose eigenphase gap satisfies Δw=Θ(δ+)Δ_w=Θ(\sqrt{δ_+})Δ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)O(δ_{+,\min}^{-1/2})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.
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.
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.
Preparing Gibbs states through dissipative dynamics requires controlling convergence for the chosen Hamiltonian HHH and coupling operators. However, efficient implementation requires convergence guarantees from the spectral gap of the generator of the dynamics, which remains a crucial challenge. Recent results address the challenge by restricting the dynamics with structural assumptions about the Hamiltonian and its interactions. For the Chen-Kastoryano-Gilyen (CKG) construction and arbitrary finite-dimensional Hamiltonians, we prove an explicit comparison that converts a spectral gap estimate for the infinite-temperature generator into a lower bound on the spectral gap of the CKG quantum Gibbs sampler at every finite positive inverse temperature βββ. It allows a single spectral gap estimate at infinite temperature to certify convergence across Hamiltonians and temperatures. Such an estimate is often known from a classical spectral gap estimate, such as the classical random walk spectral gap. For Hodge Laplacians of simplicial complexes as Hamiltonians, we construct coupling operators whose generator at infinite temperature has the same spectral gap as a classical simplicial down-up walk. A positive spectral gap of the walk and bounded spectral width W=λmax⁡(H)−λmin⁡(H)W=λ_{\max}(H)-λ_{\min}(H)W=λmax​(H)−λmin​(H) give a generator spectral gap independent of the number of simplices at every fixed temperature. We then establish conditions under which the sampler approximately prepares zero-energy (harmonic) states in polynomial evolution time. This provides a conditional convergence guarantee for the state preparation in the thermal approach to quantum topological data analysis.
In this work we consider the problem of preparation of the stationary distribution of irreducible, time-reversible Markov chains, which is a fundamental task in algorithmic Markov chain theory. For the classical setting, this task has a complexity lower bound of Ω(δ−1)\Omega(\delta^{-1})Ω(δ−1), where δ\deltaδ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is O(δ−1)O(\sqrt{\delta^{-1}})O(δ−1​), with other dependencies contributing only logarithmically. However, this bound has only been achieved for a few special classes of Markov chains. In this work, we provide a method for the sequential preparation of stationary distributions for sequences of time-reversible NNN-state Markov chains, akin to the setting of simulated annealing methods. The complexity of preparation we achieve is O(δ−1N4)O(\sqrt{\delta^{-1}} \sqrt[4]{N})O(δ−1​4N​), neglecting logarithmic factors. While this result falls short of the conjectured optimal time, it provides a quadratic improvement over na\{i}ve approaches. Moreover, for the case when the output distributions are required to be encoded in pure quantum states we identify the settings where our algorithm is strictly optimal. The settings of slowly evolving sequences of Markov chains naturally appear in reinforcement learning, and consequently our results can be readily applied in quantum machine learning as well.
Szegedy's quantum walk quadratically accelerates reversible classical Markov chains, but extending this mechanism to efficiently implementable quantum Gibbs samplers has remained challenging beyond special classes. We present a walk-free quantum algorithm for preparing purified Gibbs states with a quadratic improvement in spectral-gap dependence for a broad class of quantum Gibbs samplers that satisfy exact Kubo-Martin-Schwinger detailed balance. Our main structural result is an explicit factorization of the corresponding parent Hamiltonian into noncommutative first-order operators. This turns purified Gibbs-state preparation into a singular-value filtering problem and enables a quantum singular value transformation algorithm with quadratically improved gap dependence under standard coherent-access and warm-start assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. Moreover, we construct noncommuting Hamiltonians with efficiently preparable warm starts whose refinement under quantum Gibbs samplers requires exponential time. For these models, our algorithm achieves an end-to-end quantum speedup over the worst-case mixing scale.
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.