Delphi.science

No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders

Source: arxiv.org/abs/2611.12718

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Guneykan Ozgul, Ruslan Shaydulin, Shreehari Sureshbabu, Jacob Watkins

arXivarxiv/2611.12718Nov 9, 2026quant-phscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.12718
curl -X POST /api/v1/records/arxiv/2611.12718/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.12718/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'