aiqbench analysis
This study demonstrates that Decoded Quantum Interferometry (DQI) faces fundamental limitations on unstructured optimization problems due to spin glass phase transitions, effectively capping its potential advantage against efficient classical algorithms. By proving that approximate message passing outperforms DQI in these regimes, the research clarifies the boundary where quantum speedups are unlikely to emerge for random combinatorial instances. These findings provide critical theoretical constraints for evaluating near-term quantum algorithmic proposals targeting discrete optimization tasks.
Spin Glass Transitions Obstruct Decoded Quantum Interferometry
arXiv:2509.14509v2 Announce Type: replace Abstract: Quantum algorithms are believed to offer advantages in solving certain hard discrete optimization problems, yet identifying when such advantages persist in explicit distributions of problem instances remains a foundational challenge. Recently, a new quantum algorithm known as Decoded Quantum Interferometry (DQI) has been proposed to solve optimization problems by decoding a corresponding LDPC error-correcting code. Although DQI exhibits quantum advantage on certain structured problem instances, the possibility for advantage on random, unstructured problem instances is less well-understood. Here we prove that, assuming decoding threshold upper bounds satisfied by state-of-the-art decoders, DQI is asymptotically obstructed by a spin glass phase transition in random local combinatorial optimization problems. This phase transition is heralded by the onset of the overlap gap property (OGP), a topological fragmentation of the near-optimal solution space widely conjectured to exactly characterize the asymptotic performance of optimal efficient classical algorithms. Our results therefore indicate that DQI, applied on the best known efficient decoders, is unlikely to exhibit quantum advantage on unstructured problem instances. We support this result by proving that approximate message passing, a classical optimization algorithm, outperforms DQI on certain problem distributions.
Abstract:Quantum algorithms are believed to offer advantages in solving certain hard discrete optimization problems, yet identifying when such advantages persist in explicit distributions of problem instances remains a foundational challenge. Recently, a new quantum algorithm known as Decoded Quantum Interferometry (DQI) has been proposed to solve optimization problems by decoding a corresponding LDPC error-correcting code. Although DQI exhibits quantum advantage on certain structured problem instances, the possibility for advantage on random, unstructured problem instances is less well-understood. Here we prove that, assuming decoding threshold upper bounds satisfied by state-of-the-art decoders, DQI is asymptotically obstructed by a spin glass phase transition in random local combinatorial optimization problems. This phase transition is heralded by the onset of the overlap gap property (OGP), a topological fragmentation of the near-optimal solution space widely conjectured to exactly characterize the asymptotic performance of optimal efficient classical algorithms. Our results therefore indicate that DQI, applied on the best known efficient decoders, is unlikely to exhibit quantum advantage on unstructured problem instances. We support this result by proving that approximate message passing, a classical optimization algorithm, outperforms DQI on certain problem distributions.
Quantum Physics (quant-ph); Disordered Systems and Neural Networks (cond-mat.dis-nn); Statistical Mechanics (cond-mat.stat-mech); Data Structures and Algorithms (cs.DS)
arXiv:2509.14509 [quant-ph]
(or arXiv:2509.14509v2 [quant-ph] for this version)
Full text under the publisher's open licence · 209 words
Related coverage
Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
arXiv · Oct 1, 2026
Gibbs state preparation through quantum decoding
arXiv · Oct 5, 2026
News
Quantum Computing Report · Jul 25, 2026
Witness Spins Transition to Spin Glass Phase at 260 Millikelvin
Quantum Zeitgeist · Jun 11, 2026