Provable Quantum--Classical Separation for Continuous Gibbs Sampling

arXiv:2608.24527v1 Announce Type: cross Abstract: We prove the first quantum--classical separation for a sampling problem over a continuous domain. For a class of Gibbs states ppropto e^{-eta E} on the torus T^d with smooth (s-Gevrey) potential and barrier amplitude alpha=e^{etaDelta}, where Delta = max E-min E, every classical algorithm---querying the value, gradient, or any higher-order derivatives of the log-density---requires Omega(alpha) 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 ilde{O}left(sqrt{alpha}right) queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, e^{Omega(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.

Related

• Diffusion-warm sampling of the XY model enables fast thermalization at scale
• On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacy
• Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
• Properties and limitations of geometric tempering for gradient flow dynamics

Source: arXiv cs.LG | 2026-08-26