Provable Quantum-Classical Separation for Continuous Gibbs Sampling
Abstract
We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states p∝ e−βE on the torus 𝕋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 Õ(√α) 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.
Related
- Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
- A Quantum/Classical Example Oracle Separation for Making Things Up
- Total Ordering of Resources: A Quantum-Classical Separation
- Contactless Continuous-Variable Quantum Optical State Conditioning With Classical MmWave Phase
- A Topology-Aware Quantum-Classical Framework for Multi-Target Active Debris Removal using Gaussian Boson Sampling
BibTeX
@misc{olivucci2026provable,
title = {{Provable Quantum-Classical Separation for Continuous Gibbs Sampling}},
author = {Enrico Olivucci and Mariia Sobchuk and Sehmimul Hoque and Jeffrey Hnybida and Kyungho W. Kim and Ala Shayeghi and Pooya Ronagh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.24527},
eprint = {2608.24527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.24527},
}
RIS
TY - UNPB
TI - Provable Quantum-Classical Separation for Continuous Gibbs Sampling
AU - Enrico Olivucci
AU - Mariia Sobchuk
AU - Sehmimul Hoque
AU - Jeffrey Hnybida
AU - Kyungho W. Kim
AU - Ala Shayeghi
AU - Pooya Ronagh
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2608.24527
UR - https://arxiv.org/abs/2608.24527
AB - We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states p∝ e^−βE on the torus 𝕋^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 Õ(√α) 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.
ER -