Provable Quantum--Classical Separation for Continuous Gibbs Sampling

Setting

• The separation holds on the torus for potentials whose scaled gradient β∇E is s-Gevrey, with 1 < s < ∞ and barrier amplitude at most α.The Gevrey parameter interpolates between real-analytic and merely smooth functions, while the theorem uses the intermediate regime.Source: §I · pp. 2–3

Main result

• Quantum sampling uses eO(√α) gradient queries versus Ω(α) classical queries at constant total-variation accuracy, yielding a quadratic advantage in barrier amplitude.The ratio becomes eΩ(d) when log α = Θ(d), including fixed multi-well potentials at low temperature β = Ω(d).Source: §I · p. 3

Significance

• The work establishes the first continuous-domain quantum–classical sampling separation and the first total-variation lower bounds with exponential-in-d hardness uniformly over arbitrary local oracles.Earlier continuous Gibbs samplers were compared only with known classical competitors, which cannot exclude faster classical algorithms.Source: §I · pp. 2–4

Classical lower bound

• The classical lower bound hides a randomly located probability-mass patch behind a flat landscape, so each local-oracle query probes only one of O(α) possible patches.This argument applies to value, gradient, and arbitrary higher-order derivative queries and works for every s > 1.Source: §I · p. 3

Quantum algorithm

• The quantum upper bound combines QSVT Gibbs-state preparation with Gevrey-controlled discretization and Fourier upsampling, while temperature annealing removes the warm-start assumption.Perturbation estimates transfer the relevant ground state and spectral gap, enabling an end-to-end sampler from a maximally mixed input using gradient queries only.Source: Figure 1 · p. 3, §I · p. 4

Setting

• The instance class consists of Gibbs states on the d-dimensional flat torus with s-Gevrey potentials, and α is the barrier amplitude determined by the energy range Δ.Smoothness controls the quantum discretization and loading cost, while α measures probability mass that can be hidden from classical search.Source: §II · pp. 4–6

Quantum upper bound

• The quantum algorithm applies QSVT with temperature annealing to a square root of the Witten Laplacian and uses a coherent gradient oracle to sample any Gibbs state at total-variation accuracy ε < 1/2.The hidden factors in its complexity are independent of d, α, ξ, ρ, and s.Source: §II · p. 6

Classical lower bound

• Every classical sampler requires Ω(α) queries on a suitable subclass, including algorithms using value, gradient, or arbitrarily high-order derivative queries.The lower bound is information-theoretic, applies to adaptive samplers, and extends to any local oracle whose answer depends only on an arbitrarily small neighborhood.Source: §II · pp. 6–7

Main result

• The main result is a √α-versus-α query-cost separation between first-order quantum and classical Gibbs samplers.The theorem applies for s > 1, d > 2s, and accuracy below a fixed cap ε0.Source: §II · p. 7

Consequences

• When log α = Ω(d) at low temperature, the query-complexity ratio becomes exponential in dimension.The stated low-temperature regime includes β = Ω(d) and log log(1/ε) = o(d).Source: §II · p. 7

III. LOWER BOUND FOR CLASSICAL GIBBS SAMPLING ON A TORUS

• Ω(α) queries are required to produce one ε-close sample in total variation for smooth Gibbs targets, even with value, gradient, or higher-derivative queries.Here α = e^(βΔ), and the guarantee applies to every instance in the target class.Source: §III · p. 7
• The hide-and-seek adversary conceals a constant-probability-mass patch in an otherwise flat potential, so missed queries reveal identical answers and probe only a bounded fraction of candidate patches.The construction is the sampling analogue of an unstructured-search query lower bound.Source: §III · p. 7
• For Gevrey exponent s ≤ 1, hiding is impossible, whereas for s > 1 it is possible at an explicitly quantified cost in potential-derivative growth.The section establishes robustness against derivative queries of every order and computes the smoothness-dependent price exactly.Source: §III · pp. 7–8

Hard instances

• Bump instances are flat outside a small patch, concentrating anomalous probability mass δ on that patch.The bump construction uses a closed patch Ω_0 and background density κ outside it.Source: A. The adversarial hide-and-seek… · p. 8

Oracle indistinguishability

• Outside the patch, the log-density is locally constant, so every queried derivative vanishes and the oracle returns the same answer for every translated bump.An algorithm’s run therefore matches the null run until its first query lands inside the hidden patch.Source: A. The adversarial hide-and-seek… · p. 8

Reduction to search

• Accurate sampling requires placing mass ≈δ on the hidden patch, effectively turning sampling into a search problem.The null-run argument separates success caused by finding the patch from blind luck in hitting it at output.Source: A. The adversarial hide-and-seek… · p. 8

Theorem III.1

• N ≥ M(δ − ε) − 1, where M = (2π)^d/v_0, for any oracle order k ∈ N ∪ {∞} and ε < δ.The bound applies to any instance class containing all translates of a bump on a patch of volume v_0.Source: A. The adversarial hide-and-seek… · p. 8

Adversarial randomization

• A uniformly random translation makes each query cover the patch with probability v_0/(2π)^d, giving ε ≥ δ − (N + 1)v_0/(2π)^d.Uniform shifting removes grid integrality constraints and achieves the optimal average coverage for a patch of volume v_0.Source: A. The adversarial hide-and-seek… · p. 9

• A three-step construction turns the Gevrey mollifier ψ_t into a smooth cell indicator and then a two-level mesa with height ratio α over a flat background.The mesa is supported on a cell, with ramps of width 2ν; decreasing ν hides its mass more effectively but increases derivative magnitudes.Source: B. The hard instances: Gevrey bumps · p. 9
• The bump family p_{ν,ℓ,α} and its torus translates form Gibbs states with smooth potentials satisfying βΔ = log α.The construction uses α > 1, 0 < ℓ < 2π, and 0 < ν ≤ ℓ/4.Source: B. The hard instances: Gevrey bumps · pp. 9–10
• The Gevrey radius is linear in the ramp width ν, and the construction embeds the hard family into the target Gibbs class under explicit ξ and ρ constraints.The radius expression depends on ν, dimension d, Gevrey order s, and (log α)^s; combining it with the hiding argument yields the class lower bounds.Source: B. The hard instances: Gevrey bumps · p. 10
• The resulting class requires the stated classical query lower bound even when algorithms query derivatives of any order, at accuracies below the construction’s threshold.This applies for s = 1 + 1/t > 1, α > e, and class parameters satisfying ξ ≥ ξ_E and ρ ≤ ρ_E(ν, ℓ, α).Source: B. The hard instances: Gevrey bumps · p. 10
• The hide-and-seek lower bound is regularity-agnostic; Gevrey membership instead certifies that these hard instances are sufficiently regular for the quantum algorithm.Later parameter choices optimize the geometry against quantum cost and derive the quantum–classical gap.Source: B. The hard instances: Gevrey bumps · p. 10

Fokker–Planck formulation

• The Gibbs distribution is recast as the unique steady state of the periodic Fokker–Planck operator, equivalently satisfying a time-independent elliptic equation.The steady-state characterization is supported for periodic potentials on a torus by [MR24].Source: §IV · p. 11

Quantum algorithm

• QSVTh prepares the discretized square-root Gibbs state by targeting the kernel of W_N, reducing the condition number from C_PI to √C_PI and yielding a quadratic speedup.The construction uses the square-root decomposition of the Witten Laplacian and applies QSVTh to its components.Source: §IV · p. 11

Warm start

• Temperature annealing removes the constant-overlap warm-start assumption required by [LDCL26].The full procedure is presented in Subsection IV B and Appendix B 3.Source: §IV · p. 11

Discretization

• On the torus, s-Gevrey smoothness controls discretization error without the dissipativity assumption used by [LDCL26] on Euclidean space.Periodic boundary conditions replace truncation of a dissipative potential to a hypercube.Source: §IV · p. 12

Rigorous guarantees

• The analysis proves ground-state proximity and spectral-gap tracking for the discretized Witten Laplacian using Davis–Kahan and operator-norm proximity.These results replace assumptions in [LDCL26], via Theorems B.12, B.15, B.14, and B.11.Source: §IV · p. 12

Quantum projection

• QSVTh projects onto the smallest-singular-value subspace of W_N by filtering between its least and second-least singular values.The filter amplifies ground states while damping higher-singular-value components, without assuming a one-dimensional kernel.Source: A. Gibbs state preparation from a warm… · p. 12

Discretization

• Under the stated potential assumptions, choosing N ∈ polylog(1/ε) makes βA_N and H_N sufficiently close, with A_N’s kernel spanned by the discretized Gibbs state.The construction uses A_N as an intermediate discretization whose Gibbs-state kernel transfers to H_N.Source: A. Gibbs state preparation from a warm… · p. 12

Spectral analysis

• The spectral gap of H_N is bounded through the gap of A_N and operator proximity, while Davis–Kahan shows its ground-state mixtures approximate the discretized Gibbs state.This supplies the spectral and perturbative justification for the projection-based preparation method.Source: A. Gibbs state preparation from a warm… · p. 12

Grid-based Gibbs sampling

• GbGS prepares an approximate discretized Gibbs state using block encodings of W_N, with a warm-start state satisfying ⟨ψ|√p⟩ ∈ Ω(1).The s-Gevrey assumption ensures the required grid size is polylogarithmic in inverse precision.Source: A. Gibbs state preparation from a warm… · p. 13

Sampling guarantee

• A single copy of the prepared state yields a sample distribution η with TV(η, σ) ≤ ε, using d · polylog(1/ε) additional elementary gates.This establishes the final sampling guarantee from the approximate Gibbs-state output.Source: A. Gibbs state preparation from a warm… · p. 13

Annealing construction

• Temperature annealing removes the warm-start requirement by repeatedly applying the filtering subroutine while increasing the inverse temperature.The construction builds on temperature-annealing strategies of [SBB07, OLMW24].Source: B. End-to-end Gibbs sampling without a… · pp. 13–14
• The protocol starts from the uniform superposition at β0 = 0 and uses steps δ = 4/(β∆2) until reaching the target temperature.The schedule takes β2∆2/4 steps and is chosen so each intermediate approximate Gibbs state is a warm start for the next filtering step.Source: B. End-to-end Gibbs sampling without a… · p. 14

End-to-end guarantee

• Theorem IV.3 guarantees a quantum algorithm that outputs η with TV(η, p) ≤ ε after Nq queries to the quantum gradient oracle O∇E.The guarantee applies to Gibbs potentials in Ws(α, ξ, ρ).Source: B. End-to-end Gibbs sampling without a… · p. 14

Complexity

• The resulting end-to-end Gibbs sampler has query complexity scaling as √α, establishing the key resource dependence for the subsequent quantum-classical separation.The complexity is stated purely in queries to O∇E and its inverse O†∇E.Source: B. End-to-end Gibbs sampling without a… · p. 14

Classical lower bound

• Fixing the hidden-mesa geometry converts the flexible classical bound into an Ω(α) bound with explicit class constants.The resulting bound is stated as Theorem V.1.Source: §V · p. 15

Separation

• The quantum upper bound is evaluated at these constants, and comparing the two costs proves Theorem II.4.The ratio uses the quantum cost (11) and the classical bound established on the corresponding subclass.Source: §V · p. 15

Quantum upper bound

• Class membership supplies full Gevrey control of p and √p, with radius of order ρ/d, enabling the algorithm’s filtering step.This establishes applicability of the quantum cost (11) to Ws(α, ξ, ρ).Source: §V · p. 15

Comparison scope

• The classical bound is evaluated on the subclass Wsα,d at the same constants, while both bounds remain worst-case query complexities in separate access models.The costs are compared on the same instance class.Source: §V · p. 15

Classical lower bound

• The lower bound holds for the s-Gevrey Gibbs-state family under the conditions s > 1 and d > 2s.The theorem is stated for a fixed constant accuracy level ε0 < 1/2.Source: A. The classical lower bound at the… · p. 15
• Ω(α) queries are necessary for classical sampling at constant accuracy, even when algorithms query derivatives of any order.The theorem considers accuracy ε ≤ ε0 < 1/2 and queries of order k ∈ N ∪ {∞}.Source: A. The classical lower bound at the… · p. 15

Accuracy regime

• Within the family of hard instances of Subsection III B, the α-dependence of (37) is best possible, meaning it is the largest one.Source: A. The classical lower bound at the… · p. 15

Class strength

• The theorem uses the largest certified class radius, and the same lower bound extends to larger classes by monotonicity under class inclusion.The extension applies when ξ ≥ 1/2 and ρ ≤ ρα,d.Source: A. The classical lower bound at the… · p. 15

Geometry optimization

• For fixed ϱ, increasing M beyond S yields at most a factor-two gain, while for fixed M, shrinking ϱ beyond Θ(1/d) gives at most a constant-factor strength improvement.These monotonicity comparisons motivate the balanced choice rather than extreme values of either geometric parameter.Source: B. Proof of the classical lower bound… · p. 16
• The balanced geometry sets M=Θ(S) and ϱ=Θ(1/d), preserving mesa strength while avoiding unnecessary loss in the bump radius.Choosing ϱ=1/2^d gives S≥(α−1)/4, while smaller ϱ improves S by at most a constant factor and reduces ρ linearly.Source: B. Proof of the classical lower bound… · p. 16

Proof of Theorem V.1

• The theorem proof verifies admissibility, establishes the classical lower bound, and then checks the class constants for the selected parameters.The admissibility step uses d>2s>2 and bounds S* between 1/4(α−1) and α−1; the subsequent step yields a lower bound linear in α.Source: B. Proof of the classical lower bound… · p. 16

Optimality of the construction

• Within the bump family, the hiding bound never exceeds α, and the chosen geometry attains it up to the constant (1−2ε_0)/16.The universal cap follows from Mδ≤1+S≤α, while the selected parameters attain the cap up to an absolute factor.Source: B. Proof of the classical lower bound… · p. 16

C. The separation theorem

• The theorem’s cost-ratio bound follows by dividing the classical lower bound by the quantum cost, yielding a dimension-dependent separation regime.The ratio has c(d) determined by the Gevrey parameter and dimension.Source: C. The separation theorem · p. 17
• When log α = Ω(d), the quadratic query gap becomes an exponential quantum advantage, with Gevrey overheads diminishing as d grows relative to s.The separation analysis attributes the s-dependence to the certified radius and polylogarithmic overheads.Source: C. The separation theorem · p. 17

1. Formal query model and proofs of the lower bound

• The query model returns the log-density value and all derivatives through a chosen order, while the lower bound extends to every local oracle.Finite-order algorithms are covered because they are special cases of order-∞ access; local answers depend only on the density near the query point.Source: §1 · pp. 20, 22
• Any algorithm achieving total-variation error ε on every translated bump requires N ≥ (2π)^d(δ − ε)/v0 − 1 queries.The null coupling shows that runs agree until the query path hits the unknown patch, and averaging over uniform translations yields the bound.Source: §1 · pp. 21–22

a. Construction of the bump family

• The profile χν,ℓ is smooth, supported on [0, ℓ]^d, vanishes outside the cell, equals one on an interior plateau, and transitions through disjoint ramps.The ramp width condition ν ≤ ℓ/4 guarantees separated boundary transitions.Source: a. Construction of the bump family · pp. 23, 25

2. Gevrey estimates for the bump potential

• The compactly supported mollifier ψt is s-Gevrey with s = 1 + 1/t and uniform amplitude and radius constants.Its derivative estimates provide the regularity needed for the bump construction.Source: a. Construction of the bump family · pp. 23, 25

a. Construction of the bump family

• The resulting density is a translated Gibbs bump with off-patch background, concentration determined by the cell volume and α, and barrier amplitude satisfying βΔ = log α.Translation preserves both the concentration and barrier properties.Source: a. Construction of the bump family · p. 26

b. Gevrey constants of the bump potential

• The bump potential has an explicit s-Gevrey seminorm with radius controlled by rt, ν, d, and (log α)^s, while α=e^(βΔ).Theorem A.16 provides the scaled-potential constants, and the additive normalization affects only the gauge-dependent order-zero term.Source: b. Gevrey constants of the bump… · p. 31

c. Density regularity from class data

• Gevrey class membership of the potential implies s-Gevrey regularity of p and √p for the quantum algorithm, with derivative control from seminorms, barrier dependence through α, and radius independent of α.The density bounds use exponentiation of the potential and give sup p ≤ α and sup √p ≤ α^1/2; the log-gradient also inherits Gevrey regularity under the stated ceiling condition.Source: c. Density regularity from class data · pp. 33–34

Appendix B: Details of the Upper Bound Results

• Appendix B fixes notation for singular values, eigenvalues, grid vectors, normalized states, diagonal matrices, and operator and vector norms used in the upper-bound analysis.The notation includes σ_min(M), σ_max(M), λ_min(M), λ_max(M), grid evaluations f_N, and normalized states |f_N⟩.Source: Appendix B · p. 34

b. Discretized Fourier differentiation

• Gevrey regularity controls Fourier-derivative, product, and chain-rule discretization errors, enabling low grid sizes for the upper-bound analysis [RSL+26].The discretized Fourier framework defines derivatives diagonally in the Fourier domain and provides truncation and chain-rule error bounds.Source: a. Fourier series · p. 35, b. Discretized Fourier differentiation · p. 36, d. Proximity of HN and AN and its… · p. 40

c. Fourier interpolation

• Fourier interpolation embeds finite Fourier data into L2(Ω), supplying the representation used for continuous-to-discrete operator analysis [LDCL26].The interpolation map is described as an isometry from CNd into L2(Ω).Source: c. Fourier interpolation · p. 37

a. Review of Gevrey regularity

• AN has a non-degenerate zero-eigenvalue ground state spanned by the discretized Gibbs weight σN.The ground state is the discretization of σ(x) = e^−βE(x).Source: c. Properties of AN · p. 39
• The smallest nonzero singular value of AN is bounded below by e^−∆β, yielding the relevant barrier-dependent spectral scale.This bound is established for βAN and uses the discretized Laplacian’s least nonzero eigenvalue together with the Gibbs-weight factors.Source: c. Properties of AN · pp. 39–40

d. Proximity of HN and AN and its implications

• When −HN and AN are ε-close in operator norm, Weyl-type perturbation bounds control HN’s two smallest singular values and its spectral gap.The comparison uses Davis–Kahan and Weyl inequalities after establishing operator-norm proximity between the discretizations.Source: d. Proximity of HN and AN and its… · p. 45
• HN and −AN are sufficiently close in operator norm to control the ground-state eigenvalue of HN.The bound is established using Weyl’s inequality, the zero least singular value of AN, and Theorem B.10’s spectral-gap estimate.Source: d. Proximity of HN and AN and its… · pp. 45–46
• Every normalized ground state |g⟩ of HN lies within eε of |√σN⟩ in Euclidean distance.The proof applies the Davis–Kahan theorem and the spectral-gap lower bound for βAN.Source: d. Proximity of HN and AN and its… · pp. 46–47

e. Quantum algorithm of [LDCL26] revamped

• The revamped algorithm reduces Gibbs sampling to finding the kernel of a discretized Witten-Laplacian Hamiltonian and applies QSVTh to its square-root factor.With suitable discretization, the ground states of the discretized Hamiltonian and factor coincide, enabling QSVTh-based Gibbs-state preparation.Source: e. Quantum algorithm of [LDCL26]… · pp. 47–48
• The square-root singular values yield a quadratic speedup in the QSVTh dependence on the spectral gap.The speedup follows because singular values of W_N are square roots of those of H_N.Source: e. Quantum algorithm of [LDCL26]… · p. 48
• The block-encoding of W_N uses 2 gradient-oracle queries and an additional eO(d^2) elementary gates.The normalization parameter is γ = πN^(d/β) + √(βR/2), with polylogarithmic factors suppressed in d and N.Source: e. Quantum algorithm of [LDCL26]… · p. 49
• The warm-start algorithm outputs a distribution η with TV(η, p) ≤ eε using M quantum queries to the gradient oracle or its inverse.The construction combines QSVTh, discretization-error control, block-encoding, and a resolution booster; the supplied passage does not include the displayed formula for M.Source: e. Quantum algorithm of [LDCL26]… · p. 51

3. Annealed quantum Gibbs sampling—removing the warm start

• Annealing removes the warm-start requirement by using a schedule with ℓ = β∆/2, step size δ = 2/(ℓ∆), and T = β^2∆^2/4 steps.The overlap analysis bounds the approximate state at one temperature against the next ideal Gibbs state, incorporating QSVTh approximation error.Source: §3 · pp. 54, 56

3. Annealed quantum Gibbs samplingremoving the warm start

• The algorithm removes the warm start by sequentially applying QSVTh at increasing inverse temperatures, carrying each prepared Gibbs state into the next annealing step.The annealing protocol repeatedly applies the thresholding procedure, with each step’s success probability determined by polynomial approximation and overlap with the next Gibbs state.Source: §3 · p. 56, Figure 3 · p. 59
• For κ = 1.8, the product of per-step success probabilities remains bounded away from zero across the annealing sequence.Sequential annealing multiplies the individual step-success probabilities, so the schedule is chosen to ensure a nonvanishing overall success probability.Source: §3 · p. 57
• The annealing schedule uses inverse temperatures β_k = kδ with δ = 4/(βΔ^2), while the analysis controls each step through the Fokker–Planck spectral gap.A Holley–Stroock comparison yields a spectral-gap bound, summarized as CPI ≤ βe^(βΔ), for the inverse gap used in the query analysis.Source: §3 · pp. 58–59
• The resulting quantum sampler achieves ~O(sqrt(alpha)) gradient-oracle queries while producing a distribution within ε total variation distance of the target Gibbs state.The conversion uses two gradient-oracle queries per block-encoding, with α = e^(βΔ) and discretization selected to control the final precision.Source: §3 · p. 60