arXiv:2609.40036
Cycle Codes and Decoded Quantum Interferometry
Anuj Apte, Shouvanik Chakrabarti, Andi Gu, Stephen P. Jordan, Ojas Parekh, Ruslan Shaydulin, Jacob Watkins, Noureldin Yosri, Adam Zalcman
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.
AI Summary
Decoded Quantum Interferometry (DQI) maps two-variable constraint optimization to decoding cycle codes. This paper asks whether probabilistic decoding guarantees, rather than minimum-distance bounds, improve its performance on MaxCut, Max-$k$-Cut, and Max-2-LINSAT. It derives a fixed-instance satisfaction law allowing imperfect decoding: under reliable recovery of errors and their one-coordinate modifications, optimized DQI with error-weight cutoff $pm$ approaches $F_\rho(p)=(\sqrt{\rho(1-p)}+\sqrt{(1-\rho)p})^2$, capped at $p=1-\rho$, where $\rho$ is the random-assignment satisfaction fraction. The analysis controls interference between error transitions sharing a syndrome; a separate result treats random targets. For homological cycle codes, minimum-weight decoding is NP-hard over every fixed field $q>2$, via three-dimensional matching. On Linial–Simkin logarithmic-girth $D$-regular graphs, circulation counting and likelihood comparisons establish reliable recovery below $(1-16q/D^{2/3})\delta_{\rm cyc}$ when $q/D^{2/3}\le1/32$, and asymptotically certain ML failure above $\delta_{\rm cyc}$. For uniform nonzero errors, $\delta_{\rm cyc}=(q-1)/[(D-1)(\sqrt{D+q-2}+\sqrt{D-2})^2]$, giving threshold $(q-1)/(4D^2)$ asymptotically. A path-based LP certificate gives polynomial-time recovery at a positive, alphabet-independent error rate. Reliably decoded DQI achieves exactly $1/2+1/[2(D-1)]$ for MaxCut and improvement $O(D^{-1})$ over random assignment for fixed-$k$ Max-$k$-Cut, versus a classical vector algorithm’s $\Theta(D^{-1/2})$ improvement. These comparisons exclude advantage in the analyzed regimes, not for unrestricted DQI. Nonbinary fixed-parameter ML thresholds and LP optimality remain unresolved; certified LP rates are conservative. Limits take graph size to infinity before degree or alphabet size.
Various AI models were used throughout this project, but all work done by AI was supervised and carefully checked by the authors, who take responsibility for the correctness of all claims.
Central claim may not hold: The paper's no-advantage upper bounds apply to asymptotically reliable cutoff families, not to all DQI algorithms using classical decoders, leaving nonvanishing-failure and postselected operation outside the established exclusion.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 27 (main) + 23 (appendices) pages, 2 figures, 2 tables