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
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$.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 55 pages, 12 figures