# Provable Quantum-Classical Separation for Continuous Gibbs Sampling

arXiv: https://arxiv.org/abs/2608.24527 · HTML: https://mlsanity.com/paper/2608.24527/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 25 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [How to Train Your Energy-Based Models](https://mlsanity.com/paper/2101.03288/) (2021)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [Computational Separations between Sampling and Optimization](https://mlsanity.com/paper/1911.02074/) (2019)
- [On the query complexity of sampling from non-log-concave distributions](https://mlsanity.com/paper/2502.06200/) (2025)
- [Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions](https://mlsanity.com/paper/2310.11445/) (2023)
- [Gibbs Sampling of Continuous Potentials on a Quantum Computer](https://mlsanity.com/paper/2210.08104/) (2022)
- [Operator-Level Quantum Acceleration of Non-Logconcave Sampling](https://mlsanity.com/paper/2505.05301/) (2025)

## Abstract (arXiv)

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.