Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper introduces a discrete adiabatic framework for Gibbs-state preparation in classical and quantum optimization, deriving a tracking theorem that bounds distributional error by accounting for error contraction and new error generation. This framework yields explicit step-complexity bounds and gap- and fluctuation-adapted schedules, with the weak-damping regime exhibiting $\dotβ\proptoδ(β)/V(β)$. Applying this to quantum walks reveals a quadratic improvement in gap dependence for suitably adapted schedules, achieving an adiabatic cost of $O(δ_{\min}^{-1/2})$ compared to the classical $O(δ_{\min}^{-1})$.
Quantum adiabatic algorithms can achieve quadratic speedups in Gibbs-state preparation by exploiting spectral amplification of Markov chain gaps.
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.