Title:
Exploring improvements of quantum-enhanced Markov chain Monte Carlo
Abstract:
Sampling from Boltzmann distributions is crucial in scientific computing with applications ranging from statistical physics to machine learning. Recently, Layden et al. [Nature 619, 282–287 (2023)] proposed a quantum-enhanced Markov chain Monte Carlo (MCMC) algorithm that uses quantum dynamics to propose transitions between classical states. While this algorithm showed an empirical polynomial speedup, the physical origin of the speedup remains unclear. We analyze the parameter regimes of quantum-enhanced MCMC for optimal performance and conjecture that the observed speedup is connected to the phase transition of the quantum spin glass. Additionally, we explore alternative quantum proposal strategies using classically optimized time-dependent Hamiltonian evolution. Looking forward, we expect that our empirical findings will aid future theoretical studies in understanding the precise mechanisms underlying the quantum speedup.