Provable Quantum-Classical Separation for Continuous Gibbs Sampling

We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states ppropto e-β E on the torus mathbbTd with smooth (s-Gevrey) potential and barrier amplitude α=eβDelta, where Delta = max E-min E, every classical algorithm querying the value, gradient, or any higher-order derivatives of the log-density requires Omega(α) queries to sample at constant accuracy in total variation distance, while a quantum algorithm based on quantum singular value thresholding and temperature annealing samples with tildeOleft(√αright) queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, eOmega(d), at low temperature. The classical bound is information-theoretic, holding for every classical algorithm with query access to the Gibbs potential and its derivatives at any order.