Provable Quantum--Classical Separation for Continuous Gibbs Sampling

Enrico Olivucci; Mariia Sobchuk; Sehmimul Hoque; Jeffrey Hnybida; Kyungho W. Kim; Ala Shayeghi; Pooya Ronagh

Source-linked AI summary

Provable Quantum--Classical Separation for Continuous Gibbs Sampling

Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque, Jeffrey Hnybida, Kyungho W. Kim, Ala Shayeghi, Pooya Ronagh

arXiv:2608.24527v1Aug 25, 2026quant-phcs.DScs.ETcs.LG

TL;DR

The paper asks whether quantum computation can reduce the cost of Gibbs sampling on a continuous domain. It combines a QSVT-based quantum sampler with a hide-and-seek classical lower-bound construction for s-Gevrey potentials, showing a quadratic separation in barrier amplitude that can become exponential in dimension.

Problem
Provable quantum–classical separations have lacked an established continuous-domain sampling example, while continuous Gibbs sampling is a recurring computational primitive.
Method
The paper combines QSVT-based Gibbs-state preparation with temperature annealing and a Gevrey bump-function hide-and-seek argument robust to derivative queries of every order.
Results
Ω(α) classical queries versus eO(√α) first-order quantum queries are required or sufficient at constant total-variation accuracy, respectively.
Takeaways & Limitations
The separation is quadratic in barrier amplitude and becomes eΩ(d) when log α = Θ(d), establishing the first provable quantum–classical separation for continuous-domain sampling.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper establishes a quantum–classical separation for continuous Gibbs sampling on a torus, using intermediate Gevrey smoothness to support both the quantum upper bound and classical lower bound. The separation is quadratic in barrier amplitude and can become exponential in dimension.

Motivation: Continuous-domain quantum–classical separations have lacked proven analogues of canonical discrete examples, despite recent quantum Gibbs-sampling proposals.The paper positions continuous Gibbs sampling as a recurring computational primitive with applications including Bayesian inference, generative modeling, statistical physics, and annealing-type optimization.
Gevrey regime: Controlled smoothness requires β∇E to be s-Gevrey with 1 < s < ∞, balancing quantum tractability against classical hard-instance construction.The Gevrey parameter ranges from real-analytic at s = 1 to merely smooth at s = ∞.
Classical lower bound: Ω(α) classical queries are necessary at constant total-variation accuracy for every local oracle returning E and derivatives of any order.The hide-and-seek adversary places a small anomalous probability-mass patch at a uniformly random location, so queries outside it reveal no information.
Quantum upper bound: eO(√α) quantum queries suffice with coherent first-order-oracle access, using a QSVT-based Gibbs sampler and temperature annealing.The upper bound relies on preparing a discretized Gibbs state through a discretized Witten Laplacian and then continuously upsampling.
Separation regime: The query ratio is eΩ(α^(1/2−s/d)), yielding a quadratic advantage in α and eΩ(d) separation when log α = Θ(d).The exponential-in-d regime is reached by a fixed multi-well potential at low temperature β = Ω(d), for accuracies that are not hyper-exponentially small.
Scope: The lower bound holds uniformly over arbitrary local oracles and is information-theoretic, extending prior sampling lower bounds beyond restricted target classes or accuracy measures.The paper identifies these as the first total-variation bounds with exponential-in-d hardness and the first stated uniformly over arbitrary local oracles.

II. STATEMENT OF THE MAIN RESULT

The paper defines a smooth Gibbs-sampling setting on the torus and proves a separation between classical and quantum query costs: α for classical local access versus approximately √α for a first-order quantum algorithm.

Setting: Gibbs states are defined on the d-dimensional torus with density p = e^-βE/Z, and sampling accuracy is measured in total variation distance.The potential is 2π-periodic, and the torus identifies opposite faces of [0, 2π]^d.
Classical query model: Classical algorithms query the log-density through the value and derivatives of the potential, including zeroth-, first-, and arbitrarily high-order local oracles.The formal model permits adaptive randomized algorithms, while excluding instance-dependent initialization such as a warm start.
Instance class: The instance class uses s-Gevrey derivative-growth bounds, with s > 1 allowing smooth compactly supported bumps that can hide probability mass in flat regions.The Gevrey formulation ignores the order-zero potential term because adding a constant does not change the Gibbs state.
Instance class: The barrier amplitude is α = e^βΔ, where Δ is the range of the potential and α measures the worst-case ratio of density values across the landscape.The class parameters also impose consistency constraints on the allowable smoothness radius and barrier amplitude.
Quantum upper bound: The quantum upper bound uses QSVTh applied to a square root of the Witten Laplacian, coherent gradient access, and temperature annealing.Gevrey regularity supplies bounds for both the density and its square root, which are used in the filtering step.
Main separation: Ncl = Ω(α) for classical local-oracle sampling, while a first-order quantum algorithm uses approximately √α queries up to dimension, smoothness, and precision factors.The classical lower bound is information-theoretic and applies to adaptive samplers and queries of every derivative order; the main theorem identifies the two costs as √α versus α.

III. LOWER BOUND FOR CLASSICAL GIBBS SAMPLING ON A TORUS

The classical lower bound applies to smooth Gibbs sampling on the torus under value-and-derivative query access. Its hide-and-seek construction yields linear query growth in the barrier amplitude, with Gevrey regularity setting the admissible hard-instance class.

N_cl = Ω(α) queries are required to sample the Gibbs class at constant total-variation accuracy.The bound holds for algorithms querying the potential and derivatives of any order.
The lower-bound argument hides anomalous probability mass in a patch within an otherwise flat landscape.Local queries return the same information until a query lands on the hidden patch.
The construction is regularity-agnostic for the lower bound, while class membership certifies sufficient smoothness for the quantum algorithm.The hard family is placed in the s-Gevrey class through explicit parameter conditions.

A. The adversarial hide-and-seek argument

The hide-and-seek proof randomizes the location of a probability-concentrating patch while keeping oracle responses flat outside it. Accurate sampling therefore requires finding the hidden patch or succeeding by limited blind luck.

The adversarial hide-and-seek argument: A bump distribution is flat outside a closed patch and concentrates anomalous probability mass inside it.This structure makes the patch’s location the hidden instance information.
The adversarial hide-and-seek argument: Outside the patch, the log-density is locally constant, so value and all derivative queries return the same flat answer.Every translated bump is indistinguishable at such query points.
The adversarial hide-and-seek argument: A classical run matches the instance-independent null run until its first query enters the hidden patch.The first hit reveals the patch position; before then, the transcript is identical across instances.
The adversarial hide-and-seek argument: N ≥ M(δ − ε) − 1, where M = (2π)^d/v_0 counts hiding places and ε < δ is the target total-variation error.The bound follows by averaging over uniformly shifted patches.
The adversarial hide-and-seek argument: The proof uses uniformly random shifts of tiled bump cells, removing the integrality constraint on the cell side length.This lets the adversary choose the geometric scale continuously.

B. The hard instances: Gevrey bumps

The hard instances are two-level Gevrey bump densities: a high mesa over a compact cell, smoothly connected to a flat background. Their ramp width controls the trade-off between hiding probability mass and derivative growth.

The hard instances: Gevrey bumps: s > 1 is essential for constructing Gevrey bump distributions with hidden probability mass.The construction begins with a compactly supported mollifier whose Gevrey exponent is s = 1 + 1/t.
The hard instances: Gevrey bumps: The bump is built by integrating the mollifier, multiplying smooth steps into an indicator, then shifting and normalizing a two-level mesa profile.The profile is one on an inner plateau, zero outside the cell, and monotone across ramps.
The hard instances: Gevrey bumps: The ramp width ν is the price knob: steeper ramps hide the mesa more tightly but require larger derivatives and reduce the Gevrey radius.Combining the radius constraint with the hide-and-seek theorem produces the class-specific lower bound.
The hard instances: Gevrey bumps: The mesa height ratio is α, with normalization Zν,ℓ,α and relative variables M for hiding places and S for mesa strength.The two-dimensional figure depicts the plateau and ramps geometrically.
The hard instances: Gevrey bumps: The constructed bumps are Gibbs states with smooth potentials satisfying βΔ = log α.Their translates remain in the same Gibbs family on the torus.

IV. UPPER BOUND FOR QUANTUM GIBBS SAMPLING ON A TORUS

The quantum upper bound recasts Gibbs sampling as preparing the kernel state of a discretized Fokker–Planck-related operator. QSVTh, discretization analysis, and temperature annealing close prior assumptions and yield an end-to-end oracle-query guarantee.

IV. UPPER BOUND FOR QUANTUM GIBBS SAMPLING ON A TORUS: The discretized Fokker–Planck operator has the Gibbs state as its unique steady state on the torus.The paper uses the corresponding time-independent elliptic equation as the sampling target.
IV. UPPER BOUND FOR QUANTUM GIBBS SAMPLING ON A TORUS: QSVTh prepares a state approximating |√p_N⟩ by targeting the kernel encoded by the discretized operator.The construction uses discretized components derived from the Witten-Laplacian square-root decomposition.
IV. UPPER BOUND FOR QUANTUM GIBBS SAMPLING ON A TORUS: The component-wise QSVTh construction reduces the condition number from C_PI to √C_PI, producing an operator-level quadratic speedup.This avoids applying QSVTh directly to the Witten Laplacian.
IV. UPPER BOUND FOR QUANTUM GIBBS SAMPLING ON A TORUS: Temperature annealing removes the requirement for an initial state with constant overlap with the target Gibbs state.The earlier warm-start assumption is handled by the annealing procedure.
IV. UPPER BOUND FOR QUANTUM GIBBS SAMPLING ON A TORUS: The torus and s-Gevrey setting replace Euclidean dissipativity assumptions while controlling discretization error through periodic smoothness.The resulting end-to-end complexity is expressed in queries to the gradient oracle and its inverse.

A. Gibbs state preparation from a warm start

The warm-start quantum sampler uses QSVTh on a discretized Witten-Laplacian construction to prepare an approximate Gibbs state, then converts it into a continuous sample.

Ground-state filtering: QSVTh projects onto the ground-state subspace of the discretized Witten Laplacian, whose ground states approximate the target discretized Gibbs state.The construction does not assume the discretized operator has a one-dimensional kernel; a threshold separates its smallest singular values from the rest.
Discretization: The discretized operator is compared with an auxiliary discretization whose kernel is spanned by the discretized Gibbs state.Gevrey regularity allows the operators to be made sufficiently close in operator norm at polylogarithmic grid size.
Accuracy: A spectral-gap lower bound and the Davis–Kahan theorem show that mixtures of ground states approximate the discretized Gibbs distribution.The spectral gap is transferred from the auxiliary operator to the Witten-Laplacian discretization.
Warm start: GbGS prepares an approximate discretized Gibbs state from a warm-start state with constant overlap with the target Gibbs state.The warm-start requirement is stated as ⟨ψ|√p⟩∈Ω(1).
Continuous sampling: One copy of the prepared state can be measured and continuously upsampled to produce a sample within total-variation error eε.The upsampling procedure uses d · polylog(1/eε) additional elementary gates.

B. End-to-end Gibbs sampling without a warm start

The paper removes the warm-start requirement by applying the filtered Gibbs-state preparation repeatedly along a temperature-annealing schedule. The resulting end-to-end algorithm samples the continuous Gibbs distribution using only the quantum gradient oracle.

End-to-end annealing: Temperature annealing eliminates the warm-start requirement by filtering the current approximate Gibbs state at successive inverse temperatures.The process begins from the uniform superposition at β0 = 0 and increases β in fixed increments.
Output: The final measured state is upsampled using Fourier interpolation to obtain the continuous-domain output.The algorithm’s input includes the target inverse temperature β, barrier range ∆, and target precision ε.
Annealing schedule: The annealing schedule uses steps of size δ := 4/(β∆2) and runs for β2∆2/4 steps before measurement and Fourier-interpolation upsampling.The schedule is chosen so that the filtering success probability converges.
Guarantee: The algorithm outputs a sample η satisfying TV(η, p) ≤ε using queries to the quantum gradient oracle O∇E.Theorem IV.3 gives the overall query complexity after combining discretization and annealing costs.
Query cost: The end-to-end complexity combines QSVTh costs at each annealing step with the schedule length and success probability.The resulting bound is expressed purely in queries to O∇E and its inverse O†∇E.

V. QUANTUM–CLASSICAL SEPARATION

The separation compares a classical lower bound and a quantum upper bound on the same Gevrey Gibbs-state class. The lower bound is linear in the barrier amplitude, while the quantum cost is evaluated on that same class.

Separation construction: The separation fixes the hidden-mesa geometry so the classical hide-and-seek lower bound becomes linear in the barrier amplitude α.The quantum upper bound is then evaluated at the same class parameters and compared through their query-complexity ratio.
Quantum side: The quantum cost applies because class membership provides Gevrey control of both p and √p, with a radius of order ρ/d.This regularity is consumed by the filtering step.
Common class: The classical and quantum costs are worst-case query complexities in their respective access models, evaluated on the same instance class.The comparison uses the classical lower-bound subclass and the quantum algorithm’s applicability to the larger class.

A. The classical lower bound at the separation regime

At the separation regime, the paper establishes a classical lower bound for s-Gevrey Gibbs states at constant accuracy and transfers it across larger instance classes by monotonicity.

Oracle model: The lower bound applies to algorithms using derivative queries of any order, including the order-∞ oracle.Finite-order algorithms satisfy the bound a fortiori.
Class strength: The theorem is stated at the largest certified Gevrey radius, with 1/ρα,d ≍d1+sα1/d logs α.A larger class with ξ ≥1/2 and ρ ≤ρα,d inherits the same bound by monotonicity.

B. Proof of the classical lower bound Theorem V.1

The proof optimizes a Gevrey bump geometry for hiding probability mass, balancing the number of patches, concentration, and smoothness radius to obtain a lower bound linear in α.

Geometry choice: M = Θ(S) hiding places and ramp fraction ϱ = Θ(1/d) balance concentration strength against the Gevrey radius.The balanced choice keeps the mesa strength within constant factors of its cap while avoiding unnecessary radius loss.
Admissibility: The optimized parameters satisfy S* ≤ α − 1 and produce a certified bump radius ρ = ρα,d.These estimates establish the admissibility conditions used in the theorem’s classical lower-bound step.
Lower bound: The resulting classical query lower bound is linear in α for the selected subclass of Gevrey Gibbs potentials.The proof then transfers the subfamily bound to the full instance class by inclusion monotonicity.
Optimality: Mδ ≤ 1 + S ≤ α bounds the hide-and-seek lower bound by α for every admissible bump geometry.The selected geometry attains this optimal strength up to the constant (1 − 2ε0)/16.

C. The separation theorem

The separation theorem formalizes local-oracle sampling and combines a hide-and-seek lower bound with Gevrey-certified bump constructions. The lower bound applies broadly to classical local access, including arbitrary derivative orders.

Query model: A sampling algorithm makes adaptive local-oracle queries using an instance-independent random seed and outputs a law after N queries.Order-k oracles return the log-density and derivatives through order k at the queried point.
Hide-and-seek bound: The null coupling keeps the algorithm’s transcript instance-independent until its queries hit the hidden patch.Outside the patch, the local oracle returns the same flat answer as on the null instance.
Hide-and-seek bound: N ≥ (2π)^d(δ − ε)/v0 − 1 follows when every translated bump must be sampled within total-variation error ε.The proof averages over uniformly translated patches, each of which occupies volume v0/(2π)^d.
Class transfer: The lower bound transfers from translated bumps to any larger class containing them by monotonicity of query complexity.The constructed bumps satisfy the required Gevrey class conditions and barrier amplitude.
Oracle generality: The argument holds for every local oracle, not only value-and-derivative oracles.Local answers may include functionals determined by the density in arbitrarily small neighborhoods.

b. Gevrey constants of the bump potential

The bump potential is shown to belong to the required s-Gevrey class by composing explicit derivative bounds for compactly supported mollifiers with logarithmic stability estimates.

Bump construction: The bump indicator χν,ℓ is formed from products of smoothed steps whose derivative supports remain disjoint when ν ≤ ℓ/4.This support separation enables the pointwise derivative estimates used for the composed potential.
Class parameters: ρE = rt ν / (2^d s (log α)^s) is the certified radius for the scaled Gibbs potential.The additive normalization constant changes only the zeroth-order term and leaves nonzero derivatives unchanged.
Quantum interface: The full Gevrey regularity is used by the quantum upper bound, which requires regularity of both p and √p.Class membership yields p ∈ Gs and √p ∈ Gs with corresponding rescaled parameters.

e. Quantum algorithm of [LDCL26] revamped

The revamped quantum sampler prepares the Gibbs state by discretizing a Witten-Laplacian factorization, applying QSVTh, and using annealing to supply successive warm starts.

Discretization: The discretized operator HN = WN†WN is constructed so its ground state approximates the discretized Gibbs state.The singular-value formulation enables QSVTh to target the ground state through WN.
QSVTh: Taking square roots of HN singular values yields the quadratic speedup in spectral-gap dependence for QSVTh.This is the central mechanism connecting singular-value thresholding to faster Gibbs-state preparation.
Oracle implementation: Two queries to the gradient oracle implement the block-encoding of WN, with additional eO(d^2) elementary gates.The block-encoding normalization depends on the discretization and gradient scale.
Sampling output: QSVTh outputs a state that can be converted into samples with total-variation error at most ε using one prepared state copy.The resolution booster adds d · polylog(1/ε) elementary gates.
Annealing: Repeated QSVTh applications at decreasing inverse temperatures implement annealing toward the target temperature.The previous Gibbs state supplies the warm start for the next step, and the full protocol is summarized by the annealing schedule.
End-to-end cost: The resulting annealed sampler uses Nq quantum gradient-oracle queries to achieve TV(η, p) ≤ ε for potentials in Ws(α, ξ, ρ).The total cost combines QSVTh, discretization, annealing length, and success probability.