Skip to content
Preprint

Provable Quantum-Classical Separation for Continuous Gibbs Sampling

Aug 2026 · 1 citation · 50 references
Physics Computer Science

Abstract

We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $\alpha=e^{\beta\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(\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 $\tilde{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.

View source

Similar papers

Preprint Aug 2026

Quantum Speedups for Log-Concave Sampling from Local Structure

If each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using local queries using $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number.

Cheng-Hua Liu, Qi-Sheng Wang, Zheng-Feng Ji · 0 citations
Preprint Oct 2026

Optimal query complexity for fractional quantum evolution

The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.

A. Liu, Adam Wesołowski, Jayne Thompson et al. · 0 citations
Preprint Sep 2026

A spectral gap for Metropolis-adjusted Langevin algorithm with a uniformly randomized step size

Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\, \mathrm{d} x$ on $\mathbb{R}^d$, where $U$ is continuously differentiable and $m$-strongly convex with a globally $L$-Lipschitz gradient, $0<m\leq L<\infty$, and $\kappa=L/m$. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds...

Qian Qin · 0 citations
Preprint Sep 2026

Exact High-Temperature Quantum Area Law

We prove a $\beta^{2}$ area law for the quantum mutual information of thermal states of local lattice Hamiltonians: for any bipartitioning $A|B$ and all inverse temperatures $\beta$ below a critical value $\beta^{*}$, we show $\mathcal{I}_{\beta}(A,B) \leqslant \tilde{f}(\beta)\, \beta^{2}\,|\partial_{AB}|$, where $|\p...

Ahmad Yousefi, A. Rezakhani · 0 citations
Preprint Sep 2026

Quantum Approximate Counting with Bernoulli Oracles

An upper bound of $\tilde{O}\!\big(\frac{\rho}}{\Delta\epsilon}+\frac{1}{\Delta\sqrt{\epsilon}}\big)$ queries is proved for quantum counting with bounded-error oracles, achieving a quadratic speedup over the classical sample complexity.

Chen Gao, Yong-Zhen Xu, Lvzhou Li · 0 citations
Preprint Sep 2026

Query-Optimal and Gate-Efficient Lindbladian Simulation

A one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst, and bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels.

Bo-Yang Chen, Min-Bo Gao, Xin-Zhao Wang et al. · 6 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.