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 optimal 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
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 from the evolving distribution to the instantaneous stationary state by combining two effects: contraction of previously accumulated error by the Markov dynamics and the new error generated as the stationary distribution changes from one step to the next. For Gibbs paths, this leads to explicit step-complexity bounds and to gap- and fluctuation-adapted schedules controlled by the Markov-chain spectral gap and the energy-fluctuation scale $V(β)=\sqrt{\operatorname{Var}_{π_β}(E)}$. In the weak-damping regime, the resulting schedule takes the form $\dotβ\proptoδ(β)/V(β)$. We then apply the discrete quantum adiabatic theorem to temperature-dependent Szegedy quantum walks. The quantum-walk eigenphase gap satisfies $Δ_w=Θ(\sqrtδ)$, where $δ$ is the spectral gap of the underlying Markov chain. By analysing the finite-difference terms entering the theorem, we show that this square-root spectral amplification translates into a quadratic improvement in the gap dependence only for suitably gap-adapted schedules. Under the corresponding regularity conditions, the quantum adiabatic cost scales as $O(δ_{\min}^{-1/2})$, compared with the classical $O(δ_{\min}^{-1})$ relaxation scale.

Comments
50 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•1 citation

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•2 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•5 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•9 citations

Double Localization for Quantum Gibbs Sampler Gaps: From an Abstract Framework to Finite-Group Models

Ryu Hayakawa, Angus Southwell, Caesnan M. G. Leditto +2 more

We introduce double localization, a framework for proving spectral gaps of quantum Gibbs samplers through two complementary operations: geometric localization, which selects updates supported in small spatial regions, and interface localization, which focuses on a model-defined subspace of observables while remaining geometrically global. Our abstract gap theorem combines a global bound on this subspace, called the interface, with local quantum gap estimates under quantitative coupling and geometric assembly conditions. The resulting explicit lower bound controls the gap of the full dynamics without requiring the interface to be invariant under the generator. This separation allows global estimates, including classical comparison, to be combined with local control of the remaining quantum directions. We apply the framework to Hamiltonians built from the vertex terms of Kitaev's finite-group quantum double construction, without plaquette terms, on finite simple three-regular graphs of girth at least six. For the specified local Davies dynamics, we prove an unconditional spectral-gap lower bound by a positive constant independent of graph size for every fixed nontrivial finite group and each fixed inverse temperature $β$ with $0\leβJ<\log(5/3)$, where $J>0$ is the coupling strength. For the smallest non-Abelian group $S_3$, double localization yields a positive lower bound uniform in both graph size and the entire interval $0\leβJ\le\log 3$, providing a guarantee that does not follow directly from existing results. This demonstrates how model-specific finite calculations can extend spectral-gap guarantees for the full quantum dynamics.

quant-pharXiv:2609.39802•Oct 1, 2026•1 citation
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 from the evolving distribution to the instantaneous stationary state by combining two effects: contraction of previously accumulated error by the Markov dynamics and the new error generated as the stationary distribution changes from one step to the next. For Gibbs paths, this leads to explicit step-complexity bounds and to gap- and fluctuation-adapted schedules controlled by the Markov-chain spectral gap and the energy-fluctuation scale V(β)=Var⁡πβ(E)V(β)=\sqrt{\operatorname{Var}_{π_β}(E)}V(β)=Varπβ​​(E)​. In the weak-damping regime, the resulting schedule takes the form β˙∝δ(β)/V(β)\dotβ\proptoδ(β)/V(β)β˙​∝δ(β)/V(β). We then apply the discrete quantum adiabatic theorem to temperature-dependent Szegedy quantum walks. The quantum-walk eigenphase gap satisfies Δw=Θ(δ)Δ_w=Θ(\sqrtδ)Δw​=Θ(δ​), where δδδ is the spectral gap of the underlying Markov chain. By analysing the finite-difference terms entering the theorem, we show that this square-root spectral amplification translates into a quadratic improvement in the gap dependence only for suitably gap-adapted schedules. Under the corresponding regularity conditions, the quantum adiabatic cost scales as O(δmin⁡−1/2)O(δ_{\min}^{-1/2})O(δmin−1/2​), compared with the classical O(δmin⁡−1)O(δ_{\min}^{-1})O(δmin−1​) relaxation scale.
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.
We introduce double localization, a framework for proving spectral gaps of quantum Gibbs samplers through two complementary operations: geometric localization, which selects updates supported in small spatial regions, and interface localization, which focuses on a model-defined subspace of observables while remaining geometrically global. Our abstract gap theorem combines a global bound on this subspace, called the interface, with local quantum gap estimates under quantitative coupling and geometric assembly conditions. The resulting explicit lower bound controls the gap of the full dynamics without requiring the interface to be invariant under the generator. This separation allows global estimates, including classical comparison, to be combined with local control of the remaining quantum directions. We apply the framework to Hamiltonians built from the vertex terms of Kitaev's finite-group quantum double construction, without plaquette terms, on finite simple three-regular graphs of girth at least six. For the specified local Davies dynamics, we prove an unconditional spectral-gap lower bound by a positive constant independent of graph size for every fixed nontrivial finite group and each fixed inverse temperature βββ with 0≤βJ<log⁡(5/3)0\leβJ<\log(5/3)0≤βJ<log(5/3), where J>0J>0J>0 is the coupling strength. For the smallest non-Abelian group S3S_3S3​, double localization yields a positive lower bound uniform in both graph size and the entire interval 0≤βJ≤log⁡30\leβJ\le\log 30≤βJ≤log3, providing a guarantee that does not follow directly from existing results. This demonstrates how model-specific finite calculations can extend spectral-gap guarantees for the full quantum dynamics.