Cycle Codes and Decoded Quantum Interferometry

@misc{apte2026cycle,
  title = {{Cycle Codes and Decoded Quantum Interferometry}},
  author = {Anuj Apte and Shouvanik Chakrabarti and Andi Gu and Stephen P. Jordan and Ojas Parekh and Ruslan Shaydulin and Jacob Watkins and Noureldin Yosri and Adam Zalcman},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40036},
  eprint = {2609.40036},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40036},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Cycle Codes and Decoded Quantum Interferometry
AU  - Anuj Apte
AU  - Shouvanik Chakrabarti
AU  - Andi Gu
AU  - Stephen P. Jordan
AU  - Ojas Parekh
AU  - Ruslan Shaydulin
AU  - Jacob Watkins
AU  - Noureldin Yosri
AU  - Adam Zalcman
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40036
UR  - https://arxiv.org/abs/2609.40036
AB  - 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.
ER  -