Quantum Critical Enhancement of Classical Sampling

In this work, we analyze the performance of the quantum-enhanced Markov chain Monte Carlo (MCMC) algorithm, which samples from a Boltzmann distribution of a classical Hamiltonian [Layden, David, et al. Nature 619.7969 (2023)]. This hybrid algorithm is a Markov chain over a classical configuration space, where new configurations are proposed through a projectively measured quantum evolution. This process has guaranteed convergence to a target equilibrium distribution, independent of the quality of the evolution, making it well suited for implementation on a near-term quantum device. Previous numerical studies of the performance of this algorithm on a prototypical spin glass model show an improvement in mixing time compared to classical MCMC in the low-temperature limit. Here, we investigate the nature of this improvement through an analysis of the bottlenecks of the Markov chain. We show the speedup observed numerically is due to the critical thermalization behaviour of the quantum evolution. We support our analysis with numerical investigations of the algorithmic performance on the Sherrington-Kirkpatrick and p-spin model.