Operator-level quantum acceleration of non-logconcave sampling

Abstract

Sampling from probability distributions of the form σ ∝ e − β V , where V is a continuous potential, is a fundamental task across physics, chemistry, biology, computer science, and statistics. However, when V is nonconvex, the resulting distribution becomes non-logconcave, and classical methods such as Langevin dynamics often exhibit poor performance. We introduce a quantum algorithm that provably accelerates a broad class of continuous-time sampling dynamics. For Langevin dynamics, our method encodes the target Gibbs measure into the amplitudes of a quantum state, identified as the kernel of a block matrix derived from a factorization of the Witten Laplacian operator. This connection enables Gibbs sampling via singular value thresholding and yields up to a quartic quantum speedup over best-known classical Langevin-based methods in the non-logconcave setting. Building on this framework, we further develop the first quantum algorithm that accelerates replica exchange Langevin diffusion, a widely used method for sampling from complex, rugged energy landscapes.