Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We demonstrate that Gibbs sampling for classical Ising $k$-spin glasses can be framed as a quantum decoding problem, where achievable temperatures depend on decoder performance. In the shattered phase beyond the dynamical transition, topological barriers obstruct standard algorithms, but Decoded Quantum Interferometry (DQI) with a quantum decoder, and a classical Prange-based algorithm, can overcome these barriers. Specifically, for $D=\alpha k$ with $\alpha>1$, both methods achieve sampling at inverse temperatures $β < \tanh^{-1}(1/\alpha)$ for large $k$, significantly exceeding the dynamical threshold.
Quantum interferometry shatters the topological barriers that trap classical algorithms in the disordered phase of spin glasses, enabling sampling at temperatures far below the dynamical transition.
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\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $β_{\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=α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 $β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.