Cycle Codes and Decoded Quantum Interferometry

Abstract: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.

arXiv:2609.40036 [quant-ph]

(or arXiv:2609.40036v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.40036 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.