Skip to content

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

Sep 2026 · arXiv.org · Vol abs/2609.40345 · 2 citations · 74 references
Physics Computer Science Mathematics

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\H{o}s-R\'enyi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $\beta_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(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=\alpha k$ with fixed $\alpha>1$, both Prange's algorithm and DQI can sample at any inverse temperature $\beta<\tanh^{-1}(1/\alpha)$ for sufficiently large $k$, well beyond the dynamical threshold $\beta_{\rm dyn} \sim \sqrt{2\ln k / (\alpha k)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.