quantum-computing

Breaking the Orthogonality Barrier in Quantum LDPC Codes

Kenta Kasai

14 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractClassical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612, \leq 48]]$ quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as $10^{-8}$ on the depolarizing channel with error probability $4 \%$.Popular summaryClassical LDPC codes are central to modern communications, but their design principles are difficult to transfer to quantum error correction because quantum parity checks must satisfy an additional commutation constraint. We show how to impose this constraint only on the active part of a construction built from affine permutation matrices. The resulting quantum LDPC codes retain regular sparse structure and large girth while avoiding the structural low-weight logical operators that arise in conventional parent-matrix constructions. As a demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612,\leq 48]]$ code. Sum-product BP with low-complexity post-processing reaches a frame error rate of $10^{-8}$ at a $4\%$ depolarizing error probability. This provides a route for bringing mature classical LDPC design methods into high-rate quantum error correction.► BibTeX data@article{Kasai2026breaking, doi = {10.22331/q-2026-09-09-2205}, url = {https://doi.org/10.22331/q-2026-09-09-2205}, title = {Breaking the {O}rthogonality {B}arrier in {Q}uantum {LDPC} {C}odes}, author = {Kasai, Kenta}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2205}, month = sep, year = {2026} }► References [1] R. G. Gallager. ``Low-density parity-check codes''. MIT Press. Cambridge, MA (1963). https://doi.org/10.7551/mitpress/4347.001.0001 [2] S. Kudekar, T. J. Richardson, and R. L. Urbanke. ``Spatially coupled ensembles universally achieve capacity under belief propagation''. IEEE Transactions on Information Theory 59, 7761–7813 (2013). https://doi.org/10.1109/TIT.2013.2280915 [3] T. J. Richardson and R. L. Urbanke. ``The capacity of low-density parity-check codes under message-passing decoding''. IEEE Transactions on Information Theory 47, 599–618 (2001). https://doi.org/10.1109/18.910577 [4] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke. ``Design of capacity-approaching irregular low-density parity-check codes''. IEEE Transactions on Information Theory 47, 619–637 (2001). https://doi.org/10.1109/18.910578 [5] T. J. Richardson and R. L. Urbanke. ``Modern coding theory''.

Cambridge University Press. Cambridge, UK (2008). https://doi.org/10.1017/CBO9780511791338 [6] T. J. Richardson. ``Error floors of LDPC codes''. In Proc. 41st Annual Allerton Conference on Communication, Control, and Computing. (2003). url: https://www.ideals.illinois.edu/items/138728. https://www.ideals.illinois.edu/items/138728 [7] R. M. Tanner. ``A recursive approach to low complexity codes''. IEEE Transactions on Information Theory 27, 533–547 (1981). https://doi.org/10.1109/TIT.1981.1056404 [8] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. ``Sparse-graph codes for quantum error correction''. IEEE Transactions on Information Theory 50, 2315–2330 (2004). https://doi.org/10.1109/TIT.2004.834737 [9] D. Poulin and Y. Chung. ``On the iterative decoding of sparse quantum codes''. Quantum Information and Computation 8, 987–1000 (2008). https://doi.org/10.26421/QIC8.10-8 [10] J.-P. Tillich and G. Zémor. ``Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength''. IEEE Transactions on Information Theory 60, 1193–1202 (2014). https://doi.org/10.1109/TIT.2013.2292061 [11] A. A. Kovalev and L. P. Pryadko. ``Quantum kronecker sum-product low-density parity-check codes with finite rate''. Physical Review A 88, 012311 (2013). https://doi.org/10.1103/PhysRevA.88.012311 [12] R. Wang and L. P. Pryadko. ``Distance bounds for generalized bicycle codes''. Symmetry 14, 1348 (2022). https://doi.org/10.3390/sym14071348 [13] O. A. Mostad, H.-Y. Lin, E. Rosnes, D.-S. Lee, and C.-Y. Lai. ``Advancing finite-length quantum error correction using generalized bicycle codes''. In Proc. 13th International Symposium on Topics in Coding (ISTC). Pages 1–5. Los Angeles, CA, USA (2025). https://doi.org/10.1109/ISTC65386.2025.11154497 [14] H.-K. Lin, X. Liu, P. K. Lim, and L. P. Pryadko. ``Single-shot and two-shot decoding with generalized bicycle codes'' (2025). arXiv:2502.19406. https://doi.org/10.48550/arXiv.2502.19406 arXiv:2502.19406 [15] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A 86, 032324 (2012). https://doi.org/10.1103/PhysRevA.86.032324 [16] M. Hagiwara and H. Imai. ``Quantum quasi-cyclic LDPC codes''. In Proc. IEEE International Symposium on Information Theory (ISIT). Pages 806–810. Nice, France (2007). arXiv:quant-ph/0701020. https://doi.org/10.1109/ISIT.2007.4557323 arXiv:quant-ph/0701020 [17] D. G. M. Mitchell, R. Smarandache, and Jr. Costello, D. J. ``Quasi-cyclic LDPC codes based on pre-lifted protographs''. IEEE Transactions on Information Theory 60, 5856–5874 (2014). https://doi.org/10.1109/TIT.2014.2342735 [18] M.-H. Hsieh, T. A. Brun, and I. Devetak. ``Entanglement-assisted quantum quasi-cyclic low-density parity-check codes''. Physical Review A 79, 032340 (2009). https://doi.org/10.1103/PhysRevA.79.032340 [19] D. Komoto and K. Kasai. ``Quantum error correction near the coding theoretical bound''. npj Quantum Information 11, 154 (2025). https://doi.org/10.1038/s41534-025-01090-1 [20] F. Amirzade, D. Panario, and M.-R. Sadeghi. ``Girth analysis of quantum quasi-cyclic LDPC codes''. Problems of Information Transmission 60, 71–89 (2024). https://doi.org/10.1134/S0032946024020017 [21] K. Kasai. ``Quantum error correction with girth-16 non-binary LDPC codes via affine permutation construction''. In Proc. 13th International Symposium on Topics in Coding (ISTC). Pages 1–5. Los Angeles, CA, USA (2025). https://doi.org/10.1109/ISTC65386.2025.11154564 [22] D. Ostrev, D. Orsucci, F. Lazaro, and B. Matuz. ``Classical product code constructions for quantum calderbank–shor–steane codes''. Quantum 8, 1420 (2024). https://doi.org/10.22331/q-2024-07-22-1420 [23] A. R. Calderbank and P. W. Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098–1105 (1996). https://doi.org/10.1103/PhysRevA.54.1098 [24] A. Steane. ``Multiple-particle interference and quantum error correction''. Proceedings of the Royal Society of London A 452, 2551–2577 (1996). https://doi.org/10.1098/rspa.1996.0136 [25] D. Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997). https://doi.org/10.48550/arXiv.quant-ph/9705052 arXiv:quant-ph/9705052 [26] K. Kasai. ``Quantum error correction exploiting degeneracy to approach the hashing bound'' (2025). arXiv:2506.15636. https://doi.org/10.48550/arXiv.2506.15636 arXiv:2506.15636 [27] J. Thorpe. ``Low-density parity-check (LDPC) codes constructed from protographs''. Technical Report 42-154. IPN (2003). [28] M. Fossorier. ``Quasi-cyclic low-density parity-check codes from circulant permutation matrices''. IEEE Transactions on Information Theory 50, 1788–1793 (2004). https://doi.org/10.1109/TIT.2004.831841 [29] M. Gholami and M. Alinia. ``High-performance binary and non-binary low-density parity-check codes based on affine permutation matrices''. IET Communications 9, 2114–2123 (2015). https://doi.org/10.1049/iet-com.2014.1231 [30] R. Yoshida and K. Kasai. ``Linear permutation polynomial codes''. In 2019 IEEE International Symposium on Information Theory (ISIT). Pages 66–70. IEEE (2019). https://doi.org/10.1109/ISIT.2019.8849422 [31] S. Myung, K. Yang, and D. S. Park. ``A combining method of structured LDPC codes from affine permutation matrices''. In Proc. IEEE Int. Symp. Information Theory (ISIT). Pages 674–678. (2006). https://doi.org/10.1109/ISIT.2006.261870 [32] P. Auer, N. Cesa-Bianchi, and P. Fischer. ``Finite-time analysis of the multiarmed bandit problem''. Machine Learning 47, 235–256 (2002). https://doi.org/10.1023/A:1013689704352 [33] Kenta Kasai. ``A factor-graph formulation of CSS syndrome decoding: Joint BP and four-state BP'' (2026). arXiv:2605.05132. https://doi.org/10.48550/arXiv.2605.05132 arXiv:2605.05132 [34] K. Kasai, M. Hagiwara, H. Imai, and K. Sakaniwa. ``Quantum error correction beyond the bounded distance decoding limit''. IEEE Transactions on Information Theory 58, 1223–1230 (2012). https://doi.org/10.1109/TIT.2011.2167593 [35] M. P. C. Fossorier and S. Lin. ``Soft-decision decoding of linear block codes based on ordered statistics''. IEEE Transactions on Information Theory 41, 1379–1396 (1995). https://doi.org/10.1109/18.412683 [36] J. Zhang and M. P. C. Fossorier. ``A modified weighted bit-flipping decoding of low-density parity-check codes''. IEEE Communications Letters 8, 165–167 (2004). https://doi.org/10.1109/LCOMM.2004.825737 [37] R. M. Tanner. ``Minimum-distance bounds by graph analysis''. IEEE Transactions on Information Theory 47, 808–821 (2001). https://doi.org/10.1109/18.910591 [38] David J. C. MacKay. ``Information theory, inference, and learning algorithms''.

Cambridge University Press. Cambridge, UK (2003). url: https://www.inference.org.uk/itila/book.html. https://www.inference.org.uk/itila/book.htmlCited byCould not fetch Crossref cited-by data during last attempt 2026-09-09 08:00:07: Could not fetch cited-by data for 10.22331/q-2026-09-09-2205 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-09-09 08:00:20: Cannot retrieve data from ADS due to rate limitations.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractClassical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612, \leq 48]]$ quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as $10^{-8}$ on the depolarizing channel with error probability $4 \%$.Popular summaryClassical LDPC codes are central to modern communications, but their design principles are difficult to transfer to quantum error correction because quantum parity checks must satisfy an additional commutation constraint. We show how to impose this constraint only on the active part of a construction built from affine permutation matrices. The resulting quantum LDPC codes retain regular sparse structure and large girth while avoiding the structural low-weight logical operators that arise in conventional parent-matrix constructions. As a demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612,\leq 48]]$ code. Sum-product BP with low-complexity post-processing reaches a frame error rate of $10^{-8}$ at a $4\%$ depolarizing error probability. This provides a route for bringing mature classical LDPC design methods into high-rate quantum error correction.► BibTeX data@article{Kasai2026breaking, doi = {10.22331/q-2026-09-09-2205}, url = {https://doi.org/10.22331/q-2026-09-09-2205}, title = {Breaking the {O}rthogonality {B}arrier in {Q}uantum {LDPC} {C}odes}, author = {Kasai, Kenta}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2205}, month = sep, year = {2026} }► References [1] R. G. Gallager. ``Low-density parity-check codes''. MIT Press. Cambridge, MA (1963). https://doi.org/10.7551/mitpress/4347.001.0001 [2] S. Kudekar, T. J. Richardson, and R. L. Urbanke. ``Spatially coupled ensembles universally achieve capacity under belief propagation''. IEEE Transactions on Information Theory 59, 7761–7813 (2013). https://doi.org/10.1109/TIT.2013.2280915 [3] T. J. Richardson and R. L. Urbanke. ``The capacity of low-density parity-check codes under message-passing decoding''. IEEE Transactions on Information Theory 47, 599–618 (2001). https://doi.org/10.1109/18.910577 [4] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke. ``Design of capacity-approaching irregular low-density parity-check codes''. IEEE Transactions on Information Theory 47, 619–637 (2001). https://doi.org/10.1109/18.910578 [5] T. J. Richardson and R. L. Urbanke. ``Modern coding theory''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Breaking the Orthogonality Barrier in Quantum LDPC Codes

Tags

Source Information