Metraipolis › archive › dc_7f189663ee50

Cycle Codes and Decoded Quantum Interferometry — arXiv:2609.40036

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40036
License (as archived)
CC0-1.0
Archived
2026-10-07T15:22:00.211Z
SHA-256 of the archived text
511a8c48946dbe000371073c2ddf2f9782fc340abadf9e55ae114a0c0a4296b4
Stable URL of this page
https://metraipolis.com/documento/dc_7f189663ee50

How to cite

Cycle Codes and Decoded Quantum Interferometry — arXiv:2609.40036 — arXiv (en), https://arxiv.org/abs/2609.40036 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7f189663ee50 (Metraipolis archive dc_7f189663ee50, sha256 511a8c48946dbe000371073c2ddf2f9782fc340abadf9e55ae114a0c0a4296b4)
BibTeX
@misc{dc7f189663ee50,
  title = {Cycle Codes and Decoded Quantum Interferometry — arXiv:2609.40036},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40036},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7f189663ee50; sha256 511a8c48946dbe000371073c2ddf2f9782fc340abadf9e55ae114a0c0a4296b4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40036. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed that DQI achieves a nontrivial satisfaction fraction guarantee only on linear-girth graphs, for which MaxCut is classically easy. However, these no-go results rely on minimum distance assumptions that do not represent true decodability thresholds for common noise channels, thus underestimating actual DQI performance. To estimate the true performance, we derive DQI satisfaction guarantees in the presence of imperfect decoding for fixed instances and generalize prior results for random instances. We then study homological cycle codes over arbitrary finite fields, and show that minimum-weight decoding is NP-hard for every field of size $q>2$, in contrast with known results for binary cycle codes. On the Linial--Simkin ensemble of regular graphs with logarithmic girth, we prove maximum-likelihood recovery bounds and a strong converse for a family of non-uniform additive noise channels. Moreover, LP decoders provide polynomial-time recovery of a positive fraction of randomly located errors with arbitrary values. These results allow us to prove upper and lower bounds on the approximate optima achievable by DQI when restricted to classical decoders. These bounds rule out quantum advantage in the regimes we analyze but also identify a family of regular Max-$k$-Cut instances on which DQI efficiently achieves a nontrivial satisfaction fraction guarantee.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-01 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.40036 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:53:56.785Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).