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

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(\beta)=\sqrt{\operatorname{Var}_{\pi_\beta}(E)}$. In the weak-damping regime, the resulting schedule takes the form $\dot{\beta}\propto\delta(\beta)/V(\beta)$. We then apply the discrete quantum adiabatic theorem to temperature-dependent Szegedy quantum walks. The quantum-walk eigenphase gap satisfies $\Delta_w=\Theta(\sqrt{\delta})$, where $\delta$ 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(\delta_{\min}^{-1/2})$, compared with the classical $O(\delta_{\min}^{-1})$ relaxation scale.

arXiv:2610.06268 [quant-ph]

(or arXiv:2610.06268v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.06268 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.