Id: arxiv/2611.12718 Url: https://arxiv.org/abs/2611.12718 Tags: quant-ph, cs.DS Score: 0 Title: No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders Domain: quant-ph Source: arxiv Authors: Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Guneykan Ozgul, Ruslan Shaydulin, Shreehari Sureshbabu, Jacob Watkins Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-09 Page: https://delphi.science/r/arxiv/2611.12718 Decoded quantum interferometry (DQI) reduces optimization of sparse linear constraint problems, and sampling from their Gibbs measures, to decoding a linear code from a quantum state. We study DQI on random $D$-regular $k$-sparse instances with $k\ge3$, for which local decoders such as belief propagation with quantum messages (BPQM) are commonly used. Such decoders estimate a typical codeword symbol using only the qudits within logarithmic distance of it. Our main insight is that the thresholds of the decoding problem induced by DQI correspond to phase transitions of the Gibbs measure that…