26th Australian Institute of Physics Congress and the Australian and New Zealand Conference on Optics and Photonics

Variance-based schedules for Gibbs-state preparation for classical and quantum optimisation algorithms

Not scheduled

20m

Belinda Hutchinson Building (The University of Sydney )

Contributed Oral AIP | Quantum Science and Technology (QST)

Description

A Gibbs state assigns higher probability to low-energy configurations and lower probability to high-energy ones, making it a natural tool for searching for good solutions of optimisation problems. Classically, this idea appears in simulated annealing, where one slowly lowers the temperature using Markov chain Monte Carlo methods. Quantum computation offers the possibility of speeding up parts of this process, but it is important to understand precisely where such speedups can and cannot arise.

In this work, we develop a Markov-chain analogue of the discrete adiabatic theorem and apply it to Gibbs-state preparation. We prove tracking bounds for a sequence of reversible Markov operators, each having a Gibbs distribution as its stationary distribution. For Gibbs states, the relevant local quantity is the energy variance: the distribution changes most rapidly in temperature regions where the energy fluctuates strongly. This leads naturally to variance-based schedules, combined with the Markov-chain gap, which measures how quickly the chain relaxes to equilibrium.
We then derive, for the first time, the application of the quantum discrete adiabatic theorem to quantum walks encoding reversible Markov chains. In this setting, the coherent quantum Gibbs state is the instantaneous eigenstate of the qubitized walk, and its variation along the inverse-temperature path is again governed by the energy variance. However, the quantum adiabatic schedule may depend on the square of the quantum phase gap. Since this phase gap is itself the square root of the classical Markov-chain gap, the resulting quantum schedule can have the same gap dependence as the classical Markov-chain schedule.

This clarifies why previous classical and quantum simulated-annealing results may appear to match, depending on the implementation and cost model. Our framework identifies the roles of variance, Markov-chain gaps, and quantum phase gaps in Gibbs-state preparation, and provides a unified adiabatic perspective on classical and quantum annealing schedules.