Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
Abstract
We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising k-spin glasses (or Max-k-XORSAT) on random Erdős-Rényi hypergraphs with average degree D≥ k. In a temperature range beginning asymptotically at the predicted dynamical phase transition, βdyn(k,D) = √((2ln k)/D)× [1+ok→∞(1)], we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when D=αk with fixed α>1, both Prange's algorithm and DQI can sample at any inverse temperature β< tanh−1(1/α) for sufficiently large k, well beyond the dynamical threshold βdyn ∼ √(2ln k / (αk)). Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.
Related
- COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
- Jensen-Bregman split Gibbs sampling
- Non-Uniform Random Scans in Gibbs Sampling and CAVI
- Learning to Replace MCMC in Split-Gibbs Diffusion Posterior Sampling via Deep Unfolding
- On skew-symmetric distributions and their use in Monte Carlo sampling algorithms: coordinate-free, Gibbs-style and manifold versions of the Barker proposal
BibTeX
@misc{zhou2026gibbs,
title = {{Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry}},
author = {Leo Zhou and Noah Shutty and Mark Sellke and Stephen P. Jordan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40345},
eprint = {2609.40345},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40345},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
AU - Leo Zhou
AU - Noah Shutty
AU - Mark Sellke
AU - Stephen P. Jordan
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40345
UR - https://arxiv.org/abs/2609.40345
AB - We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising k-spin glasses (or Max-k-XORSAT) on random Erdős-Rényi hypergraphs with average degree D≥ k. In a temperature range beginning asymptotically at the predicted dynamical phase transition, β_dyn(k,D) = √((2ln k)/D)× [1+o_k→∞(1)], we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when D=αk with fixed α>1, both Prange's algorithm and DQI can sample at any inverse temperature β< tanh^−1(1/α) for sufficiently large k, well beyond the dynamical threshold β_dyn ∼ √(2ln k / (αk)). Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.
ER -