arXiv:2609.40250
An (almost) efficient classical algorithm for sampling from typical Gibbs states
Saleh Naghdi, Eric R. Anschuetz
Abstract
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.
AI Summary
The paper asks whether sampling computational-basis measurement outcomes of typical quantum Gibbs states can exhibit an exponential quantum advantage even when local observables are classically tractable. It studies the dense, randomly coupled quantum $p$-spin ensemble and combines algorithmic stochastic localization (ASL) with Barvinok interpolation. The main unconditional result is a sampling reduction for any distribution $p$ on $\{\pm1\}^N$. Given uniformly accurate estimates of the means of all exponential tilts $p_{\mathbf y}(\mathbf z)\propto e^{\mathbf y\cdot\mathbf z}p(\mathbf z)$, discretized stochastic localization followed by randomized rounding samples within total variation error $\epsilon$. The stated parameters require $O(N^5/\epsilon^4)$ mean-estimator calls and normalized $\ell_2$ estimation error $O(\epsilon^2/N^{5/2})$. The proof uses Girsanov’s theorem to control path-law errors and rounding to obtain total variation guarantees. For quantum $p$-spin Gibbs distributions, tilted means can be estimated in $N^{O(\log(N/\epsilon))}$ time provided the tilted partition functions admit a uniform constant-width zero-free region. This yields a conditional quasi-polynomial-time sampler. Polymer expansions rigorously establish an untilted zero-free disk $J|\beta|\leq0.2256/\sqrt p$ for fixed $p\geq3$, with high probability, and zero-freeness of the expected tilted partition function. The required instance-wise zero-freeness uniformly over tilts remains conjectural; the untilted concentration argument fails with nonzero tilt. Extension down to the spin-glass transition relies on physics heuristics, as does comparison with quantum mixing barriers there. The sampling task concerns measurement outcomes in a fixed product basis, not preparation of the quantum state.
We prompted ChatGPT 5.6 to circumvent this Lipschitz continuity assumption, which led to it telling us the main idea behind the current proof of Theorem~\ref{thm:num_guar_sl}.
Central claim may not hold: The abstract's quasi-polynomial-time sampling guarantee is established only conditionally on an unproved zero-free region uniform over all real tilts, even at sufficiently high constant temperature. The proved untilted zero-free disk and zero-freeness of the expected tilted partition function do not establish the instance-wise tilted zero-freeness required by the sampler. The abstract's claim that efficient quantum algorithms fail at the spin-glass transition exceeds the body's heuristic evidence concerning quantum open-system mixing times. The second-moment proof asserts exp(2q)B(β)≤1/2 at its advertised radius, but its own definitions give approximately 9.10 for q=3 and J=1, invalidating that step of the numerical-radius proof.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 34 pages; added references to the diffusion modeling literature, fixed typos and inconsistencies in notation