The DOI matches its DataCite record.
Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes
Open accessPreprint — published as 10.1109/tit.2026.3715538
Abstract
Decoding quantum error-correcting codes is a key challenge in enabling fault-tolerant quantum computation. In the classical setting, linear programming (LP) decoders offer provable performance guarantees and can leverage fast practical optimization algorithms. Although LP decoders have been proposed for quantum codes, their performance and limitations remain relatively underexplored. In this work, we uncover a key limitation of LP decoding for quantum low-density parity-check (LDPC) codes: certain constant-weight error patterns lead to ambiguous fractional solutions that cannot be resolved through independent rounding. To address this issue, we incorporate a post-processing technique known as ordered statistics decoding (OSD), which significantly enhances LP decoding performance in practice. Our results show that LP decoding, when augmented with OSD, can outperform belief propagation with the same post-processing for intermediate code sizes of up to hundreds of qubits. These findings suggest that LP-based decoders, equipped with effective post-processing, offer a promising approach for decoding near-term quantum LDPC codes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“This issue can be improved by adding post-processing steps [181].”
From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [181]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 66
- [1][1] P. W. Shor, 'Scheme for reducing decoherence in quantum computer memory,' Phys. Rev. A , vol. 52, pp. R2493-R2496, Oct 1995. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.52.R2493 - · DOI · Paper page
- [2][2] J. Preskill, 'Reliable quantum computers,' Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , vol. 454, no. 1969, pp. 385-410, 1998. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1998.0167 - · DOI · Paper page
- [3][3] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information , 10th ed. Cambridge: Cambridge university press, 2010. -
- [4][4] N. P. Breuckmann and J. N. Eberhardt, 'Quantum low-density paritycheck codes,' PRX Quantum , vol. 2, p. 040101, Oct 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PRXQuantum.2.040101 - · DOI · Paper page
- [5][5] D. Gottesman, 'Fault-tolerant quantum computation with constant overhead,' Quantum Information and Computation , vol. 14, no. 15-16, p. 1339-1371, Nov. 2014. [Online]. Available: http://www.rintonpress. com/journals/doi/QIC14.15-16-5.html -
- [6][6] S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, 'High-threshold and low-overhead fault-tolerant quantum memory,' Nature , vol. 627, no. 8005, p. 778-782, Mar. 2024. [Online]. Available: https://www.nature.com/articles/s41586-024-07107-7 -
- [7][7] Q. Xu, J. P. Bonilla Ataides, C. A. Pattison, N. Raveendran, D. Bluvstein, J. Wurtz, B. Vasi´ c, M. D. Lukin, L. Jiang, and H. Zhou, 'Constantoverhead fault-tolerant quantum computation with reconfigurable atom arrays,' Nature Physics , vol. 20, no. 7, p. 1084-1090, Jul. 2024. [Online]. Available: https://www.nature.com/articles/s41567-024-02479-z -
- [8][8] Q. T. Nguyen and C. A. Pattison, 'Quantum fault tolerance with constant-space and logarithmic-time overheads,' ser. STOC '25. New York, NY, USA: Association for Computing Machinery, 2025, p. 730-737. [Online]. Available: https://doi.org/10.1145/3717823.3718318 - · DOI
- [9][9] H. Yamasaki and M. Koashi, 'Time-efficient constant-space-overhead fault-tolerant quantum computation,' Nature Physics , vol. 20, no. 2, p. 247-253, Feb. 2024. [Online]. Available: https://www.nature.com/ articles/s41567-023-02325-8 -
- [10][10] J.-P. Tillich and G. Z´ emor, 'Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength,' IEEE Transactions on Information Theory , vol. 60, no. 2, pp. 1193-1202, 2014. [Online]. Available: https://doi.org/10.1109/TIT. 2013.2292061 - · DOI
- [11][11] M. B. Hastings, J. Haah, and R. O'Donnell, 'Fiber bundle codes: breaking the n1/2 polylog(n) barrier for quantum ldpc codes,' in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , ser. STOC 2021. New York, NY, USA: Association for Computing Machinery, 2021, p. 1276-1288. [Online]. Available: https://doi.org/10.1145/3406325.3451005 - · DOI
- [12][12] P. Panteleev and G. Kalachev, 'Quantum ldpc codes with almost linear minimum distance,' IEEE Transactions on Information Theory , vol. 68, no. 1, pp. 213-229, 2022. [Online]. Available: https: //doi.org/10.1109/TIT.2021.3119384 - · DOI
- [13][13] N. P. Breuckmann and J. N. Eberhardt, 'Balanced product quantum codes,' IEEE Transactions on Information Theory , vol. 67, no. 10, pp. 6653-6674, 2021. [Online]. Available: https://doi.org/10.1109/TIT. 2021.3097347 - · DOI
- [14][14] P. Panteleev and G. Kalachev, 'Asymptotically good quantum and locally testable classical ldpc codes,' in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , ser. STOC 2022. New York, NY, USA: Association for Computing Machinery, 2022, p. 375-388. [Online]. Available: https://doi.org/10.1145/3519935.3520017 - · DOI · Paper page
- [15][15] A. Leverrier and G. Zemor, ' Quantum Tanner codes ,' in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . Los Alamitos, CA, USA: IEEE Computer Society, Nov. 2022, pp. 872-883. [Online]. Available: https://doi.ieeecomputersociety. org/10.1109/FOCS54457.2022.00117 - · DOI · Paper page
- [16][16] I. Dinur, M.-H. Hsieh, T.-C. Lin, and T. Vidick, 'Good quantum ldpc codes with linear time decoders,' in Proceedings of the 55th Annual ACM Symposium on Theory of Computing , ser. STOC 2023. New York, NY, USA: Association for Computing Machinery, 2023, p. 905-918. [Online]. Available: https://doi.org/10.1145/3564246.3585101 - · DOI
- [17][17] A. Leverrier, J.-P. Tillich, and G. Z´ emor, 'Quantum expander codes,' in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , 2015, pp. 810-824. [Online]. Available: https://doi.org/10.1109/FOCS.2015.55 - · DOI
- [18][18] O. Fawzi, A. Grospellier, and A. Leverrier, 'Constant overhead quantum fault-tolerance with quantum expander codes,' in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , 2018, pp. 743-754. [Online]. Available: https://doi.org/10.1109/FOCS. 2018.00076 - · DOI
- [19][19] S. Gu, C. A. Pattison, and E. Tang, 'An efficient decoder for a linear distance quantum ldpc code,' in Proceedings of the 55th Annual ACM Symposium on Theory of Computing . Orlando FL USA: ACM, Jun. 2023, p. 919-932. [Online]. Available: https://dl.acm.org/doi/10.1145/3564246.3585169 - · DOI
- [20][20] A. Leverrier and G. Z´ emor, 'Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes,' ACM Trans. Algorithms , May 2024, just Accepted. [Online]. Available: https://doi.org/10.1145/3663763 - · DOI
- [21][21] S. Gu, E. Tang, L. Caha, S. H. Choe, Z. He, and A. Kubica, 'Single-shot decoding of good quantum ldpc codes,' Communications in Mathematical Physics , vol. 405, no. 3, p. 85, Mar. 2024. [Online]. Available: https://doi.org/10.1007/s00220-024-04951-6 - · DOI
- [22][22] P. Panteleev and G. Kalachev, 'Degenerate Quantum LDPC Codes With Good Finite Length Performance,' Quantum , vol. 5, p. 585, Nov. 2021. [Online]. Available: https://doi.org/10.22331/q-2021-11-22-585 - · DOI · Paper page
- [23][23] J. Roffe, D. R. White, S. Burton, and E. Campbell, 'Decoding across the quantum low-density parity-check code landscape,' Phys. Rev. Res. , vol. 2, p. 043423, Dec 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevResearch.2.043423 - · DOI · Paper page
- [24][24] N. Delfosse, V. Londe, and M. E. Beverland, 'Toward a union-find decoder for quantum ldpc codes,' IEEE Transactions on Information Theory , vol. 68, no. 5, pp. 3187-3199, 2022. [Online]. Available: https://doi.org/10.1109/TIT.2022.3143452 - · DOI
- [25][25] M. Sipser and D. Spielman, 'Expander codes,' IEEE Transactions on Information Theory , vol. 42, no. 6, pp. 1710-1722, 1996. [Online]. Available: https://doi.org/10.1109/18.556667 - · DOI
- [26][26] J. Pearl, 'Reverend bayes on inference engines: a distributed hierarchical approach,' in Proceedings of the Second AAAI Conference on Artificial Intelligence , ser. AAAI'82. AAAI Press, 1982, p. 133-136. -
- [27][27] F. Kschischang, B. Frey, and H.-A. Loeliger, 'Factor graphs and the sum-product algorithm,' IEEE Transactions on Information Theory , vol. 47, no. 2, pp. 498-519, 2001. [Online]. Available: https://doi.org/10.1109/18.910572 - · DOI · Paper page
- [28][28] J. Feldman, M. J. Wainwright, and D. R. Karger, 'Using linear programming to decode binary linear codes,' IEEE Trans. Inform. Theory , vol. 51, no. 3, pp. 954-972, 2005. [Online]. Available: https://doi.org/10.1109/TIT.2004.842696 - · DOI
- [29][29] J. Feldman, 'Decoding error-correcting codes via linear programming,' Thesis, Massachusetts Institute of Technology, 2003. [Online]. Available: https://dspace.mit.edu/handle/1721.1/42831 -
- [31][31] J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright, 'LP decoding corrects a constant fraction of errors,' IEEE Transactions on Information Theory , vol. 53, no. 1, pp. 82-89, 2007. [Online]. Available: https://doi.org/10.1109/TIT.2006.887523 - · DOI
- [32][32] J. Feldman and C. Stein, 'Lp decoding achieves capacity,' in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , ser. SODA '05. USA: Society for Industrial and Applied Mathematics, 2005, p. 460-469. -
- [33][33] O. Fawzi, L. Grou` es, and A. Leverrier, 'Linear programming decoder for hypergraph product quantum codes,' in 2020 IEEE Information Theory Workshop (ITW) , 2021, pp. 1-5. [Online]. Available: https://doi.org/10.1109/ITW46852.2021.9457611 - · DOI
- [34][34] J. X. Li and P. O. Vontobel, 'LP decoding of quantum stabilizer codes,' in 2018 IEEE International Symposium on Information Theory (ISIT) , 2018, pp. 1306-1310. [Online]. Available: https: //doi.org/10.1109/ISIT.2018.8437905 - · DOI
- [35][35] L. Grou` es, 'Decoding of LDPC quantum codes,' Theses, Sorbonne Universit´ e, Dec. 2022. [Online]. Available: https://theses.hal.science/ tel-04018968 -
- [36][36] D. J. C. MacKay and R. M. Neal, 'Good codes based on very sparse matrices,' in Cryptography and Coding , C. Boyd, Ed. Berlin, Heidelberg: Springer, 1995, p. 100-111. [Online]. Available: https://doi.org/10.1007/3-540-60693-9 13 - · DOI
- [37][37] D. J. MacKay and R. M. Neal, 'Near shannon limit performance of low density parity check codes,' Electronics Letters , vol. 32, pp. 1645-1646, 1996. [Online]. Available: https://digital-library.theiet.org/ doi/abs/10.1049/el%3A19961141 - · DOI
- [38][38] D. MacKay, 'Good error-correcting codes based on very sparse matrices,' IEEE Transactions on Information Theory , vol. 45, no. 2, pp. 399-431, 1999. [Online]. Available: https://doi.org/10.1109/18.748992 - · DOI
- [39][39] D. Poulin and Y. Chung, 'On the iterative decoding of sparse quantum codes,' Quantum Information and Computation , vol. 8, no. 10, p. 986-1000, Nov. 2008. [Online]. Available: http://www.rintonpress.com/ journals/doi/QIC8.10-8.html -
- [40][40] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, 'Fifteen years of quantum ldpc coding and improved decoding strategies,' IEEE Access , vol. 3, pp. 2492-2519, 2015. [Online]. Available: https://doi.org/10.1109/ACCESS.2015.2503267 - · DOI
- [41][41] N. Raveendran and B. Vasi´ c, 'Trapping Sets of Quantum LDPC Codes,' Quantum , vol. 5, p. 562, Oct. 2021. [Online]. Available: https://doi.org/10.22331/q-2021-10-14-562 - · DOI
- [42][42] A. R. Calderbank and P. W. Shor, 'Good quantum error-correcting codes exist,' Phys. Rev. A , vol. 54, pp. 1098-1105, Aug 1996. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.54.1098 - · DOI · Paper page
- [43][43] A. Steane, 'Multiple-particle interference and quantum error correction,' Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , vol. 452, no. 1954, pp. 2551-2577, Nov 1996. [Online]. Available: https://doi.org/10.1098%2Frspa.1996. 0136 - · DOI
- [44][44] A. Y. Kitaev, 'Fault-tolerant quantum computation by anyons,' Annals of Physics , vol. 303, no. 1, p. 2-30, Jan. 2003. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0003491602000180 -
- [45][45] R. M. Karp, Reducibility among Combinatorial Problems . Boston, MA: Springer US, 1972, p. 85-103. [Online]. Available: https: //doi.org/10.1007/978-1-4684-2001-2 9 - · DOI
- [46][46] A. Schrijver, Theory of linear and integer programming , nachdr. ed., ser. Wiley-Interscience series in discrete mathematics and optimization. Chichester Weinheim: Wiley, 2011. -
- [47][47] M. Fossorier and S. Lin, 'Soft-decision decoding of linear block codes based on ordered statistics,' IEEE Transactions on Information Theory , vol. 41, no. 5, pp. 1379-1396, 1995. [Online]. Available: https://doi.org/10.1109/18.412683 - · DOI
- [48][48] M. Fossorier, 'Iterative reliability-based decoding of low-density parity check codes,' IEEE Journal on Selected Areas in Communications , vol. 19, no. 5, pp. 908-917, 2001. [Online]. Available: https: //doi.org/10.1109/49.924874 - · DOI
- [49][49] C. Daskalakis, A. G. Dimakis, R. M. Karp, and M. J. Wainwright, 'Probabilistic analysis of linear programming decoding,' IEEE Transactions on Information Theory , vol. 54, no. 8, pp. 3565-3578, 2008. [Online]. Available: https://doi.org/10.1109/TIT.2008.926452 - · DOI
- [50][50] M. Pacenti and B. Vasi´ c, 'Quantum margulis codes,' in 2024 60th Annual Allerton Conference on Communication, Control, and Computing , 2024, pp. 1-5. [Online]. Available: https://doi.org/10.1109/ Allerton63246.2024.10735283 -
- [51][51] J. Alman, R. Duan, V. V. Williams, Y. Xu, Z. Xu, and R. Zhou, More Asymmetry Yields Faster Matrix Multiplication . Society for Industrial and Applied Mathematics, 2025, pp. 2005-2039. [Online]. Available: https://epubs.siam.org/doi/abs/10.1137/1.9781611978322.63 - · DOI
- [52][52] M. B. Cohen, Y. T. Lee, and Z. Song, 'Solving linear programs in the current matrix multiplication time,' in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , ser. STOC 2019. New York, NY, USA: Association for Computing Machinery, 2019, p. 938-942. [Online]. Available: https://doi.org/10.1145/3313276.3316303 - · DOI
- [53][53] M. Fredman and R. Tarjan, 'Fibonacci heaps and their uses in improved network optimization algorithms,' in 25th Annual Symposium onFoundations of Computer Science, 1984. , 1984, pp. 338-346. [Online]. Available: https://doi.org/10.1109/SFCS.1984.715934 - · DOI
- [54][54] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms , 2nd ed. The MIT Press, 2001. -
- [55][55] J. Edmonds, 'Paths, trees, and flowers,' Canadian Journal of Mathematics , vol. 17, p. 449-467, 1965. [Online]. Available: https://doi.org/10.4153/CJM-1965-045-4 - · DOI · Paper page
- [56][56] A. G. Fowler, A. C. Whiteside, and L. C. L. Hollenberg, 'Towards practical classical processing for the surface code,' Phys. Rev. Lett. , vol. 108, p. 180501, May 2012. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.108.180501 - · DOI
- [57][57] O. Higgott and C. Gidney, 'Sparse Blossom: correcting a million errors per core second with minimum-weight matching,' Quantum , vol. 9, p. 1600, Jan. 2025. [Online]. Available: https://doi.org/10.22331/ q-2025-01-20-1600 -
- [58][58] Y. Wu and L. Zhong, 'Fusion blossom: Fast mwpm decoders for qec,' in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) , vol. 01, 2023, pp. 928-938. [Online]. Available: https://doi.org/10.1109/QCE57702.2023.00107 - · DOI · Paper page
- [61][61] D. Burshtein and I. Goldenberg, 'Improved linear programming decoding and bounds on the minimum distance of ldpc codes,' in 2010 IEEE Information Theory Workshop , 2010, pp. 1-5. [Online]. Available: https://doi.org/10.1109/CIG.2010.5592887 - · DOI
- [62][62] M. H. Taghavi N. and P. H. Siegel, 'Adaptive methods for linear programming decoding,' IEEE Transactions on Information Theory , vol. 54, no. 12, pp. 5396-5410, 2008. [Online]. Available: https://doi.org/10.1109/TIT.2008.2006384 - · DOI
- [63][63] A. G. Dimakis and M. J. Wainwright, 'Guessing facets: Polytope structure and improved lp decoder,' in 2006 IEEE International Symposium on Information Theory , 2006, pp. 1369-1373. [Online]. Available: https://doi.org/10.1109/ISIT.2006.262070 - · DOI
- [64][64] K. Yang, J. Feldman, and X. Wang, 'Nonlinear programming approaches to decoding low-density parity-check codes,' IEEE Journal on Selected Areas in Communications , vol. 24, no. 8, pp. 1603-1613, 2006. [Online]. Available: https://doi.org/10.1109/JSAC.2006.879405 - · DOI
- [65][65] S. Barman, X. Liu, S. Draper, and B. Recht, 'Decomposition methods for large scale lp decoding,' in 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , 2011, pp. 253-260. [Online]. Available: https://doi.org/10.1109/Allerton.2011.6120176 - · DOI
- [66][66] Y. Wang, J. S. Yedidia, and S. C. Draper, 'Multi-stage decoding of ldpc codes,' in 2009 IEEE International Symposium on Information Theory , 2009, pp. 2151-2155. [Online]. Available: https://doi.org/10. 1109/ISIT.2009.5205786 -
- [67][67] A. deMarti iOlius, I. Etxezarreta Martinez, J. Roffe, and J. Etxezarreta Martinez, 'An almost-linear time decoding algorithm for quantum ldpc codes under circuit-level noise,' npj Quantum Information , 2026. [Online]. Available: https: //www.nature.com/articles/s41534-026-01292-1 -
- [68][68] T. Hillmann, L. Berent, A. O. Quintavalle, J. Eisert, R. Wille, and J. Roffe, 'Localized statistics decoding for quantum lowdensity parity-check codes,' Nature Communications , vol. 16, no. 1, p. 8214, 2025. [Online]. Available: https://www.nature.com/articles/ s41467-025-63214-7 -
- [69][69] C. Gidney, 'Stim: a fast stabilizer circuit simulator,' Quantum , vol. 5, p. 497, Jul. 2021. [Online]. Available: https://doi.org/10.22331/ q-2021-07-06-497 -
Cited by
Sorted by citations
Quantum error correction and fault tolerance: A comprehensive tutorial
Spencer, D. J., Jain, S. P., Tanggara, A., Sun, Z., Haug, T., Khu, D., & Bharti, K. (2026) · arXiv
Metadata
- Authors
- Gu, S., & Soleimanifar, M.
- Affiliations
- Yale University (US)
- California Institute of Technology (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2025
- Volume
- 72
- Issue
- 10
- Pages
- 7604-7618
- ISSN
- 0018-9448 (ISSN-L)
- arXiv
- 2508.04769
- OpenAlex
- W7169851400
- Cited by
- 2
- References
- 0
- Citations by year
- 2026: 2
- FWCI
- 6.93
- Type
- journal article
- Language
- en
- Open access
- green
- doi.org
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- National Science Foundation
- U.S. Department of Energy
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Keywords
- quantum LDPC codes, quantum error correction, decoding performance, code capacity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes. https://app.cochat.ai/papers/10.48550/arxiv.2508.04769
- The paper
- Gu, S., & Soleimanifar, M. (2025). Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes. arXiv. https://doi.org/10.48550/arxiv.2508.04769