Trapping Sets of Quantum LDPC Codes

Nithin Raveendran and Bane Vasić

Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85721, USA

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.

Quantum low-density parity-check (QLDPC) codes have recently gained popularity as an important class of quantum error correction codes due to their ability to realize scalable fault-tolerant quantum computers with constant overhead and are decodable using efficient iterative decoders. However, QLDPC code’s decoding performance is impacted by short cycles and detrimental graphical configurations present in their code graph. Such a performance degradation at low noise values – referred to as error floor effect will be severe especially in the case of practically useful finite length QLDPC codes. In classical LDPC coding literature, these harmful configurations classified as $\textit{trapping sets}$ (TSs) have been well studied and have aided to develop low-complexity iterative decoders that surpass the conventional belief propagation decoder. However, TSs have never been formally studied in the context of QLDPC codes and their decoding. In this work, we introduce the concept of $\textit{Quantum Trapping Sets}$ (QTSs) by investigating the failure configurations for syndrome-based iterative decoders. We establish a systematic methodology by which one can identify and classify 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. As a summary, we observe two types of QTSs – one is similar to classical TSs and the other is referred to as symmetric stabilizer TSs – these are unique to QLDPC codes. The properties of symmetric stabilizer TSs are distinct and specific to the QLDPC decoding problem and hence, will be instrumental in exploiting the degeneracy of QLDPC codes to the decoder’s advantage. Furthermore, we demonstrate the two advantages of studying QTSs – (1) Design better QLDPC codes – ability to construct QLDPC codes devoid of harmful QTSs, (2) Design better decoders without post-processing steps – ability to devise new decoding algorithms that escape from harmful QTSs and have low error floors.

► 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] 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.

[2] 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).

[3] Josias Old and Manuel Rispler, "Generalized Belief Propagation Algorithms for Decoding of Surface Codes", Quantum 7, 1037 (2023).

[4] 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.

[5] 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).

[6] Renyu Wang and Leonid Pryadko, "Distance Bounds for Generalized Bicycle Codes", Symmetry 14 7, 1348 (2022).

[7] Sisi Miao, Alexander Schnerring, Haizheng Li, and Laurent Schmalen, 2023 IEEE Information Theory Workshop (ITW) 215 (2023) ISBN:979-8-3503-0149-6.

[8] 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.

[9] 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).

[10] 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).

[11] Hsiang-Ku Lin and Leonid P. Pryadko, "Quantum two-block group algebra codes", Physical Review A 109 2, 022407 (2024).

[12] 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).

[13] 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).

[14] Nithin Raveendran, Emmanuel Boutillon, and Bane Vasić, 2023 12th International Symposium on Topics in Coding (ISTC) 1 (2023) ISBN:979-8-3503-2611-6.

[15] 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.

[16] Kao-Yueh Kuo and Ching-Yi Lai, "Exploiting degeneracy in belief propagation decoding of quantum codes", npj Quantum Information 8 1, 111 (2022).

[17] Julien Du Crest, Mehdi Mhalla, and Valentin Savin, 2022 IEEE Information Theory Workshop (ITW) 488 (2022) ISBN:978-1-6654-8341-4.

[18] 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.

[19] Julien du Crest, Mehdi Mhalla, and Valentin Savin, "Stabilizer Inactivation for Message-Passing Decoding of Quantum LDPC Codes", arXiv:2205.06125, (2022).

[20] Kao-Yueh Kuo, I-Chun Chern, and Ching-Yi Lai, "Decoding of Quantum Data-Syndrome Codes via Belief Propagation", arXiv:2102.01984, (2021).

[21] Patricio Fuentes, "Error Correction for Reliable Quantum Computing", arXiv:2202.08599, (2022).

[22] 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-03-19 03:55:50) and SAO/NASA ADS (last updated successfully 2024-03-19 03:55:51). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Trapping Sets of Quantum LDPC Codes

  1. Pingback: The Long of The Shorts | Week Ending 10/23/2021 | Quantum Computing – The Qubit Report