Search papers, labs, and topics across Lattice.
This paper establishes the first provable quantum-classical separation for continuous Gibbs sampling by demonstrating that classical algorithms require a linear number of queries proportional to the barrier amplitude to achieve constant accuracy, while a quantum algorithm can achieve this with a significantly reduced number of queries. The findings reveal that the quantum advantage is quadratic in the barrier amplitude and grows exponentially with the dimension at low temperatures. This result underscores the limitations of classical approaches in sampling from Gibbs states, particularly in high-dimensional settings.
Classical algorithms are fundamentally outmatched by quantum methods in sampling from Gibbs states, requiring exponentially more queries as dimensions increase.
We prove the first quantum--classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-βE}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $α=e^{βΔ}$, where $Δ= \max E-\min E$, every classical algorithm---querying the value, gradient, or any higher-order derivatives of the log-density---requires $Ω(α)$ 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 $\tilde{O}\left(\sqrtα\right)$ queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, $e^{Ω(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.
