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.

AI Summary

The paper studies how annealing schedules can track changing Gibbs distributions under classical Markov dynamics and coherent quantum walks, accounting for both local relaxation and variation of the target state. For finite reversible Markov chains, an explicit discrete tracking bound follows by iterating an error recursion. It retains local spectral contraction factors, stationary-distribution increments, and comparisons between successive weighted norms. For Gibbs paths, $\|\partial_\beta\pi_\beta\|_{\pi_\beta^{-1}}=\sqrt{\operatorname{Var}_{\pi_\beta}(E)}=:V(\beta)$. A slow-variation expansion of the tracking envelope defines an effective metric with coefficient $(1-\delta)^2V^2/\delta^2$. Its constant-speed schedule satisfies $\dot\beta\propto\delta/[(1-\delta)V]$ and minimizes the associated metric-energy functional, not necessarily actual tracking or terminal preparation error. For direct products of temperature-dependent Szegedy walks, without intermediate projections, the analysis applies an existing discrete adiabatic theorem and bounds first- and second-order operator differences. Schedules $\dot\beta\propto\Delta_w^p/\|\partial_\beta W\|$, $1<p<2$, yield sufficient fixed-accuracy walk count $O(\Delta_{w,\min}^{-1})=O(\delta_{+,\min}^{-1/2})$, conditional on uniform regularity, discrete-coefficient, spectral-comparison, quadrature, and path-integral assumptions. Tests use a solvable two-state model and small Sherrington–Kirkpatrick instances, including schedule transfer from smaller systems. For paired classical–quantum tests at $n=6$–$13$, fitted step counts scale as $161.8\,2^{0.3686n}$ and $47.5\,2^{0.1828n}$, respectively. These fits do not establish asymptotic speedup or total-cost advantage. Extrapolated gaps are uncertified, and the tested quantum implementation is not uniformly covered by the theorem, notably because its preparation-unitary derivative is singular at $\beta=0$.

Little sign of AI-generated textIncrementalStrong assumptionsUnclear novelty

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

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•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 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 paper studies how annealing schedules can track changing Gibbs distributions under classical Markov dynamics and coherent quantum walks, accounting for both local relaxation and variation of the target state.
For finite reversible Markov chains, an explicit discrete tracking bound follows by iterating an error recursion. It retains local spectral contraction factors, stationary-distribution increments, and comparisons between successive weighted norms. For Gibbs paths, ∥∂βπβ∥πβ−1=Var⁡πβ(E)=:V(β)\|\partial_\beta\pi_\beta\|_{\pi_\beta^{-1}}=\sqrt{\operatorname{Var}_{\pi_\beta}(E)}=:V(\beta)∥∂β​πβ​∥πβ−1​​=Varπβ​​(E)​=:V(β). A slow-variation expansion of the tracking envelope defines an effective metric with coefficient (1−δ)2V2/δ2(1-\delta)^2V^2/\delta^2(1−δ)2V2/δ2. Its constant-speed schedule satisfies β˙∝δ/[(1−δ)V]\dot\beta\propto\delta/[(1-\delta)V]β˙​∝δ/[(1−δ)V] and minimizes the associated metric-energy functional, not necessarily actual tracking or terminal preparation error.
For direct products of temperature-dependent Szegedy walks, without intermediate projections, the analysis applies an existing discrete adiabatic theorem and bounds first- and second-order operator differences. Schedules β˙∝Δwp/∥∂βW∥\dot\beta\propto\Delta_w^p/\|\partial_\beta W\|β˙​∝Δwp​/∥∂β​W∥, 1<p<21<p<21<p<2, yield sufficient fixed-accuracy walk count O(Δw,min⁡−1)=O(δ+,min⁡−1/2)O(\Delta_{w,\min}^{-1})=O(\delta_{+,\min}^{-1/2})O(Δw,min−1​)=O(δ+,min−1/2​), conditional on uniform regularity, discrete-coefficient, spectral-comparison, quadrature, and path-integral assumptions.
Tests use a solvable two-state model and small Sherrington–Kirkpatrick instances, including schedule transfer from smaller systems. For paired classical–quantum tests at n=6n=6n=6–131313, fitted step counts scale as 161.8 20.3686n161.8\,2^{0.3686n}161.820.3686n and 47.5 20.1828n47.5\,2^{0.1828n}47.520.1828n, respectively. These fits do not establish asymptotic speedup or total-cost advantage. Extrapolated gaps are uncertified, and the tested quantum implementation is not uniformly covered by the theorem, notably because its preparation-unitary derivative is singular at β=0\beta=0β=0.
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.