Search Results

We study the parallel complexity of sampling from the high-temperature Ising mixed p-spin Gibbs measure, a canonical instance of a mean-field spin glass on the hypercube {±1}ⁿ. We propose two different algorithms for this problem, corresponding to two different regimes of accuracy. Our first algorithm is a parallel implementation of a Markov chain known as block dynamics, combined with an approximate rejection sampling step that uses an Ising model in a novel way as a proposal distribution to approximate the quadratic interaction terms of the p-spin Hamiltonian. For any ε > 0, this algorithm runs in n^{1/3} polylog(n/ε) parallel time with poly(n/ε) work, and outputs a sample whose law is ε-close to the p-spin measure in total variation distance. Our second algorithm uses Picard iterations to parallelize the Algorithmic Stochastic Localization (ASL) process of El Alaoui, Montanari, and Sellke (2025), and for any ε > ε_n, takes polylog(n/ε) parallel time and poly(n/ε) work to produce a sample that is ε-close to the p-spin measure in the normalized 2-Wasserstein metric. Here, ε_n > 0 is a threshold that goes to 0 as n → ∞. Our result constitutes a doubly exponential improvement in the ε dependence of the runtime and an exponential improvement in the ε dependence of the total work when compared to naïve ASL, whose runtime scales as exp(poly(1/ε)).