Trapping Sets of Quantum LDPC Codes
Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85721, USA
Published: | 2021-10-14, volume 5, page 562 |
Eprint: | arXiv:2012.15297v2 |
Doi: | https://doi.org/10.22331/q-2021-10-14-562 |
Citation: | Quantum 5, 562 (2021). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are attractive because their hardware complexity scales only linearly with the number of physical qubits. However, they are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. These factors significantly degrade the decoder decoding probability performance and cause so-called error floor. In this paper, we establish a systematic methodology by which one can identify and classify quantum trapping sets (QTSs) according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that the knowledge of QTSs can be used to design better QLDPC codes and decoders. Frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated for some practical finite-length QLDPC codes without requiring any post-processing.
![](https://quantum-journal.org/wp-content/uploads/2021/10/2012.15297v2.png)
Featured image: Symmetric stabilizer trapping sets are harmful for iterative decoding of QLDPC codes resulting in decoder failures. The symmetry of the subgraph combined with degenerate error patterns makes it impossible for a conventional syndrome-based iterative decoder to correctly match the syndrome.
Popular summary
► BibTeX data
► References
[1] N. Raveendran and B. Vasić. Trapping set analysis of finite-length quantum LDPC codes. In IEEE Int. Symp. on Inform. Theory, pages 1564–1569, 2021. 10.1109/ISIT45174.2021.9518154.
https://doi.org/10.1109/ISIT45174.2021.9518154
[2] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. Sparse-graph codes for quantum error correction. IEEE Trans. on Inform. Theory, 50 (10): 2315–2330, Oct. 2004. 10.1109/TIT.2004.834737.
https://doi.org/10.1109/TIT.2004.834737
[3] P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52: R2493–R2496, Oct. 1995. 10.1103/PhysRevA.52.R2493.
https://doi.org/10.1103/PhysRevA.52.R2493
[4] D. Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Inform. and Computation, 14 (15–16): 1338–1372, Nov. 2014. 10.26421/QIC14.15-16-5.
https://doi.org/10.26421/QIC14.15-16-5
[5] A. A. Kovalev and L. P. Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Phys. Rev. A, 87: 020304, Feb. 2013a. 10.1103/PhysRevA.87.020304.
https://doi.org/10.1103/PhysRevA.87.020304
[6] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. The road from classical to quantum codes: A hashing bound approaching design procedure. IEEE Access, 3: 146–176, 2015a. 10.1109/ACCESS.2015.2405533.
https://doi.org/10.1109/ACCESS.2015.2405533
[7] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Fifteen years of quantum LDPC coding and improved decoding strategies. IEEE Access, 3: 2492–2519, 2015b. 10.1109/ACCESS.2015.2503267.
https://doi.org/10.1109/ACCESS.2015.2503267
[8] J.-P. Tillich and G. Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to $n^{1/2}$. Proc. IEEE Int. Symp. on Inform. Theory, pages 799–803, Jul. 2009. 10.1109/ISIT.2009.5205648.
https://doi.org/10.1109/ISIT.2009.5205648
[9] A. Leverrier, J.-P. Tillich, and G. Zémor. Quantum expander codes. In Proc. IEEE 56th Ann. Symp. on Foundations of Computer Science, pages 810–824, Berkeley, CA, USA, Oct. 2015. 10.1109/FOCS.2015.55.
https://doi.org/10.1109/FOCS.2015.55
[10] P. Panteleev and G. Kalachev. Quantum LDPC codes with almost linear minimum distance. arXiv preprint:2012.04068, 2020. URL https://arxiv.org/abs/2012.04068.
arXiv:2012.04068
[11] K.-Y. Kuo and C.-Y. Lai. Refined belief propagation decoding of sparse-graph quantum codes. IEEE Journal on Selected Areas in Information Theory, 1 (2): 487–498, 2020. 10.1109/jsait.2020.3011758.
https://doi.org/10.1109/jsait.2020.3011758
[12] C.-Y. Lai and K.-Y. Kuo. Log-domain decoding of quantum LDPC codes over binary finite fields. IEEE Trans. on Quantum Engineering, 2021. 10.1109/TQE.2021.3113936.
https://doi.org/10.1109/TQE.2021.3113936
[13] D. Poulin and Y. Chung. On the iterative decoding of sparse quantum codes. Quantum Inform. and Computation, 8 (10): 987–1000, Nov. 2008. 10.26421/QIC8.10-8.
https://doi.org/10.26421/QIC8.10-8
[14] T. J. Richardson. Error floors of LDPC codes. In Proc. 41st Ann. Allerton Conf. Commun., Contr. and Comp., pages 1426–1435, Monticello, IL, USA, Sept. 2003. URL https://web.stanford.edu/class/ee388/papers/ErrorFloors.pdf.
https://web.stanford.edu/class/ee388/papers/ErrorFloors.pdf
[15] P. Panteleev and G. Kalachev. Degenerate quantum LDPC codes with good finite length performance. arXiv preprint:1904.02703, 2019. URL https://arxiv.org/abs/1904.02703.
arXiv:1904.02703
[16] B. Vasić, D. V. Nguyen, and S. K. Chilappagari. Chapter 6 - failures and error floors of iterative decoders. In Channel Coding: Theory, Algorithms, and Applications: Academic Press Library in Mobile and Wireless Commun., pages 299–341, Oxford, 2014. Academic Press. 10.1016/B978-0-12-396499-1.00006-6.
https://doi.org/10.1016/B978-0-12-396499-1.00006-6
[17] J. Roffe, D. R. White, S. Burton, and E. Campbell. Decoding across the quantum low-density parity-check code landscape. Phys. Rev. Research, 2: 043423, Dec. 2020. 10.1103/PhysRevResearch.2.043423.
https://doi.org/10.1103/PhysRevResearch.2.043423
[18] M. P. C. Fossorier and S. Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Trans. on Inform. Theory, 41: 1379 – 1396, 10 1995. 10.1109/18.412683.
https://doi.org/10.1109/18.412683
[19] M. Baldi, N. Maturo, E. Paolini, and F. Chiaraluce. On the use of ordered statistics decoders for low-density parity-check codes in space telecommand links. EURASIP J. Wirel. Commun. Netw., 2016 (272): 1– 15, 2016. 10.1186/s13638-016-0769-z.
https://doi.org/10.1186/s13638-016-0769-z
[20] A. Rigby, J. C. Olivier, and P. Jarvis. Modified belief propagation decoders for quantum low-density parity-check codes. Phys. Rev. A, 100: 012330, Jul. 2019. 10.1103/physreva.100.012330.
https://doi.org/10.1103/physreva.100.012330
[21] J. X. Li and P. O. Vontobel. Pseudocodeword-based decoding of quantum stabilizer codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 2888–2892, 2019. 10.1109/ISIT.2019.8849833.
https://doi.org/10.1109/ISIT.2019.8849833
[22] N. Raveendran, D. Declercq, and B. Vasić. A sub-graph expansion-contraction method for error floor computation. IEEE Trans. on Commun., 68 (7): 3984–3995, 2020. 10.1109/TCOMM.2020.2988676.
https://doi.org/10.1109/TCOMM.2020.2988676
[23] S. K. Planjery, D. Declercq, L. Danjean, and B. Vasić. Finite alphabet iterative decoders, Part I: Decoding beyond belief propagation on the binary symmetric channel. IEEE Trans. on Commun., 61 (10): 4033–4045, Nov. 2013. 10.1109/TCOMM.2013.090513.120443.
https://doi.org/10.1109/TCOMM.2013.090513.120443
[24] A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098–1105, Aug. 1996. ISSN 1094-1622. 10.1103/physreva.54.1098.
https://doi.org/10.1103/physreva.54.1098
[25] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[26] D. Gottesman. Stabilizer codes and quantum error correction. Ph.D. Dissertation, California Institute of Technology, 1997. 10.7907/rzr7-dt72. URL https://arxiv.org/abs/quant-ph/9705052.
https://doi.org/10.7907/rzr7-dt72
arXiv:quant-ph/9705052
[27] M. M. Wilde. Logical operators of quantum codes. Phys. Rev. A, 79: 062322, Jun. 2009. 10.1103/PhysRevA.79.062322.
https://doi.org/10.1103/PhysRevA.79.062322
[28] N. Raveendran, P. J. Nadkarni, S. S. Garani, and B. Vasić. Stochastic resonance decoding for quantum LDPC codes. In Proc. IEEE Int. Conf. on Commun., pages 1–6, May 2017. 10.1109/ICC.2017.7996747.
https://doi.org/10.1109/ICC.2017.7996747
[29] M. Karimi and A. H. Banihashemi. Efficient algorithm for finding dominant trapping sets of LDPC codes. IEEE Trans. on Inform. Theory, 58 (11): 6942–6958, Nov. 2012. 10.1109/TIT.2012.2205663.
https://doi.org/10.1109/TIT.2012.2205663
[30] D. V. Nguyen, S. K. Chilappagari, M. W. Marcellin, and B. Vasić. On the construction of structured LDPC codes free of small trapping sets. IEEE Trans. on Inform. Theory, 58 (4): 2280–2302, Apr. 2012. 10.1109/TIT.2011.2173733.
https://doi.org/10.1109/TIT.2011.2173733
[31] S. M. Khatami, L. Danjean, D. V. Nguyen, and B. Vasić. An efficient exhaustive low-weight codeword search for structured LDPC codes. In Proc. Inform. Theory and Applications Workshop, pages 1 – 10, San Diego, CA, USA, Feb. 10–15 2013. 10.1109/ITA.2013.6502981.
https://doi.org/10.1109/ITA.2013.6502981
[32] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Construction of quantum LDPC codes from classical row-circulant QC-LDPCs. IEEE Commun. Letters, 20 (1): 9–12, Jan. 2016. 10.1109/LCOMM.2015.2494020.
https://doi.org/10.1109/LCOMM.2015.2494020
[33] M. Hagiwara and H. Imai. Quantum quasi-cyclic LDPC codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 806–810, Jun. 2007. 10.1109/ISIT.2007.4557323.
https://doi.org/10.1109/ISIT.2007.4557323
[34] Y. Xie and J. Yuan. Reliable quantum LDPC codes over GF(4). In Proc. IEEE Globecom Workshops, pages 1–5, Dec. 2016. 10.1109/GLOCOMW.2016.7849021.
https://doi.org/10.1109/GLOCOMW.2016.7849021
[35] A. A. Kovalev and L. P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Phys. Rev. A, 88: 012311, Jul. 2013b. 10.1103/PhysRevA.88.012311.
https://doi.org/10.1103/PhysRevA.88.012311
[36] A. A. Kovalev and L. P. Pryadko. Improved quantum hypergraph-product LDPC codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 348–352, Jul. 2012. 10.1109/ISIT.2012.6284206.
https://doi.org/10.1109/ISIT.2012.6284206
[37] M. P. C. Fossorier. Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. on Inform. Theory, 50 (8): 1788–1793, Aug. 2004. 10.1109/TIT.2004.831841.
https://doi.org/10.1109/TIT.2004.831841
[38] D. E. Hocevar. A reduced complexity decoder architecture via layered decoding of LDPC codes. In Proc. IEEE Workshop on Signal Processing Systems, pages 107–112, 2004. 10.1109/SIPS.2004.1363033.
https://doi.org/10.1109/SIPS.2004.1363033
[39] E. Sharon, S. Litsyn, and J. Goldberger. Efficient serial message-passing schedules for LDPC decoding. IEEE Trans. on Inform. Theory, 53 (11): 4076–4091, 2007. 10.1109/TIT.2007.907507.
https://doi.org/10.1109/TIT.2007.907507
[40] N. Raveendran and B. Vasić. Trapping set analysis of horizontal layered decoder. In Proc. IEEE Int. Conf. on Commun., pages 1–6, May 2018. 10.1109/ICC.2018.8422965.
https://doi.org/10.1109/ICC.2018.8422965
[41] Y.-J. Wang, B. C. Sanders, B.-M. Bai, and X.-M. Wang. Enhanced feedback iterative decoding of sparse quantum codes. IEEE Trans. on Inform. Theory, 58 (2): 1231–1241, Feb. 2012. 10.1109/TIT.2011.2169534.
https://doi.org/10.1109/TIT.2011.2169534
Cited by
[1] Sana Javed, Francisco Garcia-Herrero, Bane Vasić, and Mark F. Flanagan, ICC 2024 - IEEE International Conference on Communications 1782 (2024) ISBN:978-1-7281-9054-9.
[2] Kirsten D. Morris, Tefjol Pllaha, and Christine A. Kelley, 2023 12th International Symposium on Topics in Coding (ISTC) 1 (2023) ISBN:979-8-3503-2611-6.
[3] Yun-Jiang Wang, Zhuo-Yan Xiao, Yi Zhang, Xing-Yu Xiong, and Sha Shi, "Construction of Multiple-Rate Quantum LDPC Codes Sharing One Scalable Stabilizer Circuit", IEEE Transactions on Communications 71 2, 1071 (2023).
[4] Josias Old and Manuel Rispler, "Generalized Belief Propagation Algorithms for Decoding of Surface Codes", Quantum 7, 1037 (2023).
[5] Asit Kumar Pradhan, Nithin Raveendran, Narayanan Rengaswamy, Xin Xiao, and Bane Vasić, 2023 12th International Symposium on Topics in Coding (ISTC) 1 (2023) ISBN:979-8-3503-2611-6.
[6] Dimitris Chytas, Michele Pacenti, Nithin Raveendran, Mark F. Flanagan, and Bane Vasić, "Enhanced Message-Passing Decoding of Degenerate Quantum Codes Utilizing Trapping Set Dynamics", IEEE Communications Letters 28 3, 444 (2024).
[7] Renyu Wang and Leonid Pryadko, "Distance Bounds for Generalized Bicycle Codes", Symmetry 14 7, 1348 (2022).
[8] Sisi Miao, Alexander Schnerring, Haizheng Li, and Laurent Schmalen, 2023 IEEE Information Theory Workshop (ITW) 215 (2023) ISBN:979-8-3503-0149-6.
[9] Julien du Crest, Francisco Garcia-Herrero, Mehdi Mhalla, Valentin Savin, and Javier Valls, "Check-Agnosia based Post-Processor for Message-Passing Decoding of Quantum LDPC Codes", Quantum 8, 1334 (2024).
[10] Nithin Raveendran, Narayanan Rengaswamy, Asit Kumar Pradhan, and Bane Vasic, 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 275 (2022) ISBN:978-1-6654-9113-6.
[11] Eric Huang, Arthur Pesah, Christopher T. Chubb, Michael Vasmer, and Arpit Dua, "Tailoring Three-Dimensional Topological Codes for Biased Noise", PRX Quantum 4 3, 030338 (2023).
[12] Nithin Raveendran, Javier Valls, Asit Kumar Pradhan, Narayanan Rengaswamy, Francisco Garcia-Herrero, and Bane Vasić, "Soft syndrome iterative decoding of quantum LDPC codes and hardware architectures", EPJ Quantum Technology 10 1, 45 (2023).
[13] Anqi Gong, Sebastian Cammerer, and Joseph M. Renes, 2024 IEEE International Symposium on Information Theory (ISIT) 2700 (2024) ISBN:979-8-3503-8284-6.
[14] Hsiang-Ku Lin and Leonid P. Pryadko, "Quantum two-block group algebra codes", Physical Review A 109 2, 022407 (2024).
[15] Nithin Raveendran, Narayanan Rengaswamy, Filip Rozpędek, Ankur Raina, Liang Jiang, and Bane Vasić, "Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming Bound", Quantum 6, 767 (2022).
[16] Patricio Fuentes, Josu Etxezarreta Martinez, Pedro M. Crespo, and Javier Garcia-Frias, "On the Logical Error Rate of Sparse Quantum Codes", IEEE Transactions on Quantum Engineering 3, 1 (2022).
[17] Nithin Raveendran, Emmanuel Boutillon, and Bane Vasić, 2023 12th International Symposium on Topics in Coding (ISTC) 1 (2023) ISBN:979-8-3503-2611-6.
[18] Dimitris Chytas, Nithin Raveendran, Asit Kumar Pradhan, and Bane Vasić, GLOBECOM 2023 - 2023 IEEE Global Communications Conference 1393 (2023) ISBN:979-8-3503-1090-0.
[19] Hanwen Yao, Waleed Abu Laban, Christian Häger, Alexandre Graell i Amat, and Henry D. Pfister, 2024 IEEE International Symposium on Information Theory (ISIT) 2478 (2024) ISBN:979-8-3503-8284-6.
[20] Kao-Yueh Kuo and Ching-Yi Lai, "Exploiting degeneracy in belief propagation decoding of quantum codes", npj Quantum Information 8 1, 111 (2022).
[21] Julien Du Crest, Mehdi Mhalla, and Valentin Savin, 2022 IEEE Information Theory Workshop (ITW) 488 (2022) ISBN:978-1-6654-8341-4.
[22] Julien Du Crest, Francisco Garcia-Herrero, Mehdi Mhalla, Valentin Savin, and Javier Valls, 2023 12th International Symposium on Topics in Coding (ISTC) 1 (2023) ISBN:979-8-3503-2611-6.
[23] Julien du Crest, Mehdi Mhalla, and Valentin Savin, "Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes", arXiv:2205.06125, (2022).
[24] Kao-Yueh Kuo, I-Chun Chern, and Ching-Yi Lai, "Decoding of Quantum Data-Syndrome Codes via Belief Propagation", arXiv:2102.01984, (2021).
[25] Patricio Fuentes, "Error Correction for Reliable Quantum Computing", arXiv:2202.08599, (2022).
[26] Ching-Yi Lai and Kao-Yueh Kuo, "Log-domain decoding of quantum LDPC codes over binary finite fields", arXiv:2104.00304, (2021).
The above citations are from Crossref's cited-by service (last updated successfully 2024-09-07 21:42:11) and SAO/NASA ADS (last updated successfully 2024-09-07 21:42:12). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.
Pingback: The Long of The Shorts | Week Ending 10/23/2021 | Quantum Computing – The Qubit Report