Provable Quantum–Classical Separation for Continuous Gibbs Sampling

This paper investigates whether quantum computers can provide a provable speedup for sampling from a Gibbs distribution p proportional to exp(-betaE) on a continuous domain (the d-dimensional torus). While quantum Gibbs samplers have been proposed, previous work lacked a rigorous lower bound to rule out efficient classical alternatives. The authors address this by establishing an information-theoretic lower bound for classical algorithms and a matching quantum upper bound, focusing on the barrier amplitude alpha = exp(betaDelta), where Delta is the range of the potential. The quantum approach uses quantum singular value thresholding (QSVT) combined with temperature annealing to navigate the potential landscape.

The authors prove that for a class of Gibbs states with s-Gevrey smooth potentials (where s > 1), any classical algorithm querying the potential's value or derivatives requires Omega(alpha) queries to achieve constant total variation distance accuracy. In contrast, they provide a quantum algorithm that achieves the same accuracy using O(sqrt(alpha)) queries to a gradient oracle. This quadratic advantage in the barrier amplitude becomes an exponential advantage in the dimension d when the barrier amplitude scales as exp(Omega(d)), such as in low-temperature regimes.

This is the first provable quantum-classical separation for a sampling problem over a continuous domain. It bridges a significant gap in computational complexity theory, moving beyond discrete, often contrived problems like Grover's search. By identifying the specific role of Gevrey smoothness—where analyticity is too restrictive for the lower bound and mere smoothness is too weak for the upper bound—the paper provides a clear theoretical foundation for the efficiency of quantum Gibbs sampling in scientific applications like Bayesian inference and statistical physics.