Spin Glass Transitions Obstruct Decoded Quantum Interferometry

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.