CoChat
Sign Up
PreprintCited by 2Quantum Computing Algorithms and ArchitectureError Correcting Code TechniquesCoding theory and cryptography

The DOI matches its DataCite record.

Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes

Open access
Gu, Shouzhen, Soleimanifar, Mehdi·2025·arXiv
DOI 10.48550/arxiv.2508.04769arXiv 2508.04769

Preprint — published as 10.1109/tit.2026.3715538

Open this paper in CoChat — free account

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2508.04769

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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][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][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][3] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information , 10th ed. Cambridge: Cambridge university press, 2010. -
  4. [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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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][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 -
  30. [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
  31. [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. -
  32. [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
  33. [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
  34. [35][35] L. Grou` es, 'Decoding of LDPC quantum codes,' Theses, Sorbonne Universit´ e, Dec. 2022. [Online]. Available: https://theses.hal.science/ tel-04018968 -
  35. [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
  36. [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
  37. [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
  38. [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 -
  39. [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
  40. [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
  41. [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
  42. [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
  43. [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 -
  44. [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
  45. [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. -
  46. [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
  47. [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
  48. [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
  49. [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 -
  50. [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
  51. [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
  52. [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
  53. [54][54] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms , 2nd ed. The MIT Press, 2001. -
  54. [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
  55. [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
  56. [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 -
  57. [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
  58. [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
  59. [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
  60. [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
  61. [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
  62. [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
  63. [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 -
  64. [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 -
  65. [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 -
  66. [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

Metadata

Authors
Gu, S., & Soleimanifar, M.
Affiliations
  • Yale University (US)
  • California Institute of Technology (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2025
Volume
72
Issue
10
Pages
7604-7618
ISSN
0018-9448 (ISSN-L)
DOI
10.48550/arxiv.2508.04769
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
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