arXiv:2609.40345
Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
Leo Zhou, Noah Shutty, Mark Sellke, Stephen P. Jordan
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\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.
AI Summary
Can decoded quantum interferometry (DQI) sample classical spin-glass Gibbs measures beyond barriers for stable algorithms? This paper reduces Gibbs sampling for Ising parity Hamiltonians with random signs to decoding a linear code under coherent bit-flip noise, with inverse temperature $\beta$ corresponding to error rate $\gamma=(1-\operatorname{sech}\beta)/2$. For random Erdős–Rényi Max-$k$-XORSAT with average degree $D\ge k$ and sufficiently large fixed $k$, it proves shattering, single-clause disorder chaos, failure of stable samplers in normalized Wasserstein distance, and exponential Glauber mixing time throughout $(1+\varepsilon)\sqrt{2\ln k/D}\le\beta\le\sqrt{k/(2D)}$. The proof establishes annealed free energy and a soft overlap gap in a planted model, transfers these properties to the original ensemble, and derives clustering and sensitivity to clause perturbations. DQI with an unambiguous-state-discrimination decoder achieves polynomial-time sampling with vanishing expected total-variation error whenever $D\tanh\beta<K_*(k)$, where $K_*(k)$ is a random-matrix full-row-rank threshold satisfying $K_*(k)/k\to1$. The decoder converts coherent noise into erasures recovered by Gaussian elimination. For $D=\alpha k$, $\alpha>1$, the achievable inverse-temperature threshold tends to $\operatorname{arctanh}(1/\alpha)$, while the dynamical threshold tends to zero. There is no demonstrated quantum advantage: a classical Prange-type sampler—independently retaining clauses with probability $\tanh\beta$ and sampling their linear-system solutions—achieves the identical bound. The separation concerns stable algorithms, not all algorithms. Guarantees are average-case; efficient sampling beyond replica symmetry breaking, improved decoders, and an ensemble exhibiting quantum advantage remain open.
Claude Fable 5.1 was used to implement Python code that generated the numerical data in Tables~\ref{tab:dense-betas}, \ref{tab:xorsat-grid}, and \ref{tab:xorsat-grid-reg}.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 44 pages, 1 figure, 3 tables