Operator-Level Quantum Acceleration of Non-Logconcave Sampling
This addresses a fundamental sampling problem in fields like physics and computer science, offering a novel quantum approach for complex distributions.
The paper tackles the problem of sampling from non-logconcave probability distributions, which is challenging for classical methods like Langevin dynamics, by introducing the first quantum algorithm that provably accelerates continuous-time sampling dynamics, achieving a quantum advantage in terms of the Poincaré constant.
Sampling from probability distributions of the form $σ\propto e^{-βV}$, where $V$ is a continuous potential, is a fundamental task across physics, chemistry, biology, computer science, and statistics. However, when $V$ is non-convex, the resulting distribution becomes non-logconcave, and classical methods such as Langevin dynamics often exhibit poor performance. We introduce the first 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 the first provable quantum advantage with respect to the Poincaré constant 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.