Decoded quantum interferometry breaks topological barriers in sampling
Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
Computational ComplexityData Structures and Algorithms
Summary
Sampling from complex systems, like certain magnetic models, is hard because some barriers stop usual algorithms from working well. The authors show that a method called decoded quantum interferometry (DQI) can overcome these barriers where other stable algorithms fail. They connect the problem of sampling to a quantum decoding challenge and prove that DQI can work at lower temperatures where typical methods get stuck. This work highlights how quantum techniques can help solve problems that are difficult for classical algorithms.
What this means in practice
- •For quantum algorithm designers: Improve sampling methods in complex spin systems by using decoded quantum interferometry to overcome barriers where classical stable algorithms fail.
- •For optimization algorithm developers: Design classical algorithms inspired by quantum decoding to sample effectively from hard constraint satisfaction problems beyond typical algorithmic limits.
Authors
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.