Degenerate Quantum LDPC Codes With Good Finite Length Performance

Pavel Panteleev and Gleb Kalachev

Faculty of Mechanics and Mathematics, Moscow State University, GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We study the performance of medium-length quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes with the maximal stabilizer weight much smaller than their minimum distance are considered. It is shown that with the help of OSD-like post-processing the performance of the standard belief propagation (BP) decoder on many QLDPC codes can be improved by several orders of magnitude. Using this new BP-OSD decoder we study the performance of several known classes of degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah's cubic codes. We also construct several interesting examples of short generalized bicycle codes. Some of them have an additional property that their syndromes are protected by small BCH codes, which may be useful for the fault-tolerant syndrome measurement. We also propose a new large family of QLDPC codes that contains the class of hypergraph product codes, where one of the used parity-check matrices is square. It is shown that in some cases such codes have better performance than hypergraph product codes. Finally, we demonstrate that the performance of the proposed BP-OSD decoder for some of the constructed codes is better than for a relatively large surface code decoded by a near-optimal decoder.


The conference talk at the 5th International Conference on Quantum Error Correction (QEC’19) – held from 29th July to 2nd August 2019 at Senate House in London.

Surface codes, as well as other quantum codes with geometrically local stabilizers, are usually considered as leading candidates for fault-tolerant architectures of quantum computers. However, the overhead of such architectures grows significantly with the code distance. On the other hand, quantum LDPC codes, where long-range interaction between qubits is allowed, can potentially be used to provide fault-tolerant quantum computations with constant overhead. Unfortunately, the finite length performance of the known classes of QLDPC codes is far from optimal under the state-of-the-art decoders. In the current work, we propose a new decoding algorithm called BP-OSD, which combines the standard BP decoder with a post-processing algorithm called Ordered Statistics Decoding (OSD), an idea borrowed from classical error-correcting codes. We demonstrate on many examples that this combined decoding strategy improves the error-correcting performance of the BP decoder by several orders of magnitude. We also propose a number of new QLDPC codes and show that for the standard depolarizing noise model the error-correcting performance of such codes under the BP-OSD decoder can be better than for surface codes even if the latter ones are decoded using a near-optimal decoder.

► BibTeX data

► References

[1] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 2002. doi:10.1063/​1.1499754.

[2] Michael H. Freedman and David A. Meyer. Projective plane and planar quantum codes. Foundations of Computational Mathematics, 1(3):325–332, Jul 2001. doi:10.1007/​s102080010013.

[3] H. Bombin and M. A. Martin-Delgado. Topological quantum distillation. Phys. Rev. Lett., 97:180501, Oct 2006. doi:10.1103/​PhysRevLett.97.180501.

[4] David S. Wang, Austin G. Fowler, and Lloyd C. L. Hollenberg. Surface code quantum computing with error rates over 1%. Phys. Rev. A, 83:020302, Feb 2011. doi:10.1103/​PhysRevA.83.020302.

[5] Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum likelihood decoding in the surface code. Phys. Rev. A, 90:032326, Sep 2014. doi:10.1103/​PhysRevA.90.032326.

[6] Nikolas P. Breuckmann and Barbara M. Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE Transactions on Information Theory, 62(6):3731–3744, June 2016. doi:10.1109/​TIT.2016.2555700.

[7] J. Tillich and G. Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to $n^{1/​2}$. In 2009 IEEE International Symposium on Information Theory, pages 799–803, June 2009. doi:10.1109/​ISIT.2009.5205648.

[8] Sergey Bravyi and Matthew B. Hastings. Homological product codes. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 273–282, New York, NY, USA, 2014. ACM. doi:10.1145/​2591796.2591870.

[9] A. A. Kovalev and L. P. Pryadko. Improved quantum hypergraph-product LDPC codes. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 348–352, July 2012. doi:10.1109/​ISIT.2012.6284206.

[10] Alexey A. Kovalev and Leonid P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Phys. Rev. A, 88:012311, Jul 2013. doi:10.1103/​PhysRevA.88.012311.

[11] 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, 2015. doi:10.1109/​ACCESS.2015.2503267.

[12] M. Hagiwara and H. Imai. Quantum quasi-cyclic LDPC codes. In 2007 IEEE International Symposium on Information Theory, pages 806–810, June 2007. doi:10.1109/​ISIT.2007.4557323.

[13] M. P. C. Fossorier and Shu Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41(5):1379–1396, Sep. 1995. doi:10.1109/​18.412683.

[14] M. P. C. Fossorier. Iterative reliability-based decoding of low-density parity check codes. IEEE Journal on Selected Areas in Communications, 19(5):908–917, may 2001. doi:10.1109/​49.924874.

[15] B. Dorsch. A decoding algorithm for binary block codes and $j$-ary output channels (corresp.). IEEE Transactions on Information Theory, 20(3):391–394, may 1974. doi:10.1109/​TIT.1974.1055217.

[16] Matthew B. Hastings, Jeongwan Haah, and Ryan 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, pages 1276–1288. Association for Computing Machinery, New York, NY, USA, June 2021. doi:10.1145/​3406325.3451005.

[17] Pavel Panteleev and Gleb Kalachev. Quantum LDPC codes with almost linear minimum distance. IEEE Transactions on Information Theory, pages 1–1, 2021. doi:10.1109/​TIT.2021.3119384.

[18] Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67(10):6653–6674, October 2021. doi:10.1109/​TIT.2021.3097347.

[19] Michael Freedman and Matthew Hastings. Building manifolds from quantum codes. Geometric and Functional Analysis, June 2021. doi:10.1007/​s00039-021-00567-3.

[20] Jeongwan Haah. Local stabilizer codes in three dimensions without string logical operators. Phys. Rev. A, 83:042330, Apr 2011. doi:10.1103/​PhysRevA.83.042330.

[21] D. Poulin and Yeojin C. On the iterative decoding of sparse quantum codes. Quantum Info. Comput., 8(10):987–1000, November 2008. doi:10.5555/​2016985.2016993.

[22] Y. Wang, B. C. Sanders, B. Bai, and X. Wang. Enhanced feedback iterative decoding of sparse quantum codes. IEEE Transactions on Information Theory, 58(2):1231–1241, Feb 2012. doi:10.1109/​TIT.2011.2169534.

[23] Alex Rigby, J. C. Olivier, and Peter Jarvis. Modified belief propagation decoders for quantum low-density parity-check codes. Physical Review A, 100(1):012330, July 2019. doi:10.1103/​PhysRevA.100.012330.

[24] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997. doi:10.7907/​rzr7-dt72.

[25] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54:1098–1105, Aug 1996. doi:10.1103/​PhysRevA.54.1098.

[26] A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77:793–797, Jul 1996. doi:10.1103/​PhysRevLett.77.793.

[27] R. G. Gallager. Low-Density Parity-Check Codes. M.I.T. Press, Cambridge, MA, 1963. doi:10.7551/​mitpress/​4347.001.0001.

[28] R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533–547, September 1981. doi:10.1109/​TIT.1981.1056404.

[29] F.R. Kschischang, B.J. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, February 2001. doi:10.1109/​18.910572.

[30] E. Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5–9, September 1962. doi:10.1109/​TIT.1962.1057777.

[31] Jack Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1(1):127–136, December 1971. doi:10.1007/​BF01584082.

[32] M.P.C. Fossorier, Shu Lin, and J. Snyders. Reliability-based syndrome decoding of linear block codes. IEEE Transactions on Information Theory, 44(1):388–398, January 1998. doi:10.1109/​18.651070.

[33] Raymond Laflamme, Cesar Miquel, Juan Pablo Paz, and Wojciech Hubert Zurek. Perfect quantum error correcting code. Physical Review Letters, 77(1):198–201, July 1996. doi:10.1103/​PhysRevLett.77.198.

[34] Kao-Yueh Kuo and Ching-Yi Lai. Refined belief propagation decoding of sparse-graph quantum codes. IEEE Journal on Selected Areas in Information Theory, 1(2):487–498, August 2020. doi:10.1109/​JSAIT.2020.3011758.

[35] Marc Fossorier, David Declercq, and Ezio Biglieri. Channel Coding: Theory, Algorithms, and Applications. Academic Press, July 2014. doi:10.1016/​C2011-0-07211-3.

[36] Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, 1965/​ed. doi:10.4153/​CJM-1965-045-4.

[37] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. Sparse-graph codes for quantum error correction. IEEE Transactions on Information Theory, 50(10):2315–2330, Oct 2004. doi:10.1109/​TIT.2004.834737.

[38] H Bombin, R W Chhajlany, M Horodecki, and M A Martin-Delgado. Self-correcting quantum computers. New Journal of Physics, 15(5):055023, may 2013. doi:10.1088/​1367-2630/​15/​5/​055023.

[39] Yuichiro Fujiwara. Ability of stabilizer quantum error correction to protect itself from its own imperfection. Phys. Rev. A, 90:062304, Dec 2014. doi:10.1103/​PhysRevA.90.062304.

[40] Tom Richardson. Error-floors of LDPC codes. In Proceedings of the 41st Annual Conference on Communication, Control and Computing, pages 1426–1435, 2003.

[41] Ye-Hua Liu and David Poulin. Neural belief-propagation decoders for quantum error-correcting codes. Physical Review Letters, 122(20):200501, May 2019. doi:10.1103/​PhysRevLett.122.200501.

[42] Kristine Lally and Patrick Fitzpatrick. Algebraic structure of quasicyclic codes. Discrete Applied Mathematics, 111(1):157–175, July 2001. doi:10.1016/​S0166-218X(00)00350-4.

[43] Roxana Smarandache and Pascal O. Vontobel. Quasi-cyclic LDPC codes: Influence of proto- and tanner-graph structure on minimum hamming distance upper bounds. IEEE Transactions on Information Theory, 58(2):585–607, February 2012. doi:10.1109/​TIT.2011.2173244.

[44] San Ling, Harald Niederreiter, and Patrick Solé. On the algebraic structure of quasi-cyclic codes IV: Repeated roots. Designs, Codes and Cryptography, 38:337–361, 2006. doi:10.1007/​s10623-005-1431-7.

[45] I. Dumer, A. A. Kovalev, and L. P. Pryadko. Distance verification for classical and quantum LDPC codes. IEEE Transactions on Information Theory, 63(7):4675–4686, 2017. doi:10.1109/​TIT.2017.2690381.

Cited by

[1] Armands Strikis and Lucas Berent, "Quantum Low-Density Parity-Check Codes for Modular Architectures", PRX Quantum 4 2, 020321 (2023).

[2] Pavel Panteleev and Gleb Kalachev, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 375 (2022) ISBN:9781450392648.

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

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

[5] Leonid P. Pryadko, Vadim A. Shabashov, and Valerii K. Kozin, "QDistRnd: A GAP package for computing the distance of quantum error-correcting codes", Journal of Open Source Software 7 71, 4120 (2022).

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

[7] Joschka Roffe, Lawrence Z. Cohen, Armanda O. Quintavalle, Daryus Chandra, and Earl T. Campbell, "Bias-tailored quantum LDPC codes", Quantum 7, 1005 (2023).

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

[9] Anthony Leverrier, Simon Apers, and Christophe Vuillot, "Quantum XYZ Product Codes", Quantum 6, 766 (2022).

[10] Joschka Roffe, "Towards practical quantum LDPC codes", Quantum Views 5, 63 (2021).

[11] Lucas Berent, Lukas Burgholzer, and Robert Wille, Proceedings of the 28th Asia and South Pacific Design Automation Conference 709 (2023) ISBN:9781450397834.

[12] T. R. Scruby, D. E. Browne, P. Webster, and M. Vasmer, "Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code", Quantum 6, 721 (2022).

[13] Christophe Piveteau and Joseph M. Renes, "Quantum message-passing algorithm for optimal and efficient decoding", Quantum 6, 784 (2022).

[14] Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett, and Benjamin J. Brown, "Low-overhead fault-tolerant quantum computing using long-range connectivity", Science Advances 8 20, eabn1717 (2022).

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

[16] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland, "Constant-Overhead Quantum Error Correction with Thin Planar Connectivity", Physical Review Letters 129 5, 050504 (2022).

[17] Oscar Higgott and Nikolas P. Breuckmann, "Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes", PRX Quantum 4 2, 020332 (2023).

[18] Thomas R. Scruby, Michael Vasmer, and Dan E. Browne, "Non-Pauli errors in the three-dimensional surface code", Physical Review Research 4 4, 043052 (2022).

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

[20] Nikolas P. Breuckmann and Jens Niklas Eberhardt, "Quantum Low-Density Parity-Check Codes", PRX Quantum 2 4, 040101 (2021).

[21] J. Eli Bourassa, Rafael N. Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q. Baragiola, Saikat Guha, Guillaume Dauphinais, Krishna K. Sabapathy, Nicolas C. Menicucci, and Ish Dhand, "Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer", Quantum 5, 392 (2021).

[22] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell, "Fragile boundaries of tailored surface codes and improved decoding of circuit-level noise", arXiv:2203.04948, (2022).

[23] Pavel Panteleev and Gleb Kalachev, "Quantum LDPC Codes with Almost Linear Minimum Distance", arXiv:2012.04068, (2020).

[24] Nikolas P. Breuckmann and Jens N. Eberhardt, "Balanced Product Quantum Codes", arXiv:2012.09271, (2020).

[25] Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell, "Single-Shot Error Correction of Three-Dimensional Homological Product Codes", PRX Quantum 2 2, 020340 (2021).

[26] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell, "Decoding across the quantum low-density parity-check code landscape", Physical Review Research 2 4, 043423 (2020).

[27] Eric Huang, Arthur Pesah, Christopher T. Chubb, Michael Vasmer, and Arpit Dua, "Tailoring three-dimensional topological codes for biased noise", arXiv:2211.02116, (2022).

[28] Nikolas P. Breuckmann and Vivien Londe, "Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance", arXiv:2001.03568, (2020).

[29] Ryan Babbush, Jarrod McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, "Focus beyond quadratic speedups for error-corrected quantum advantage", arXiv:2011.04149, (2020).

[30] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier, "Combining hard and soft decoders for hypergraph product codes", Quantum 5, 432 (2021).

[31] Ching-Feng Kung, Kao-Yueh Kuo, and Ching-Yi Lai, "On Belief Propagation Decoding of Quantum Codes with Quaternary Reliability Statistics", arXiv:2305.03321, (2023).

[32] Leonid P. Pryadko, "On maximum-likelihood decoding with circuit-level errors", Quantum 4, 304 (2020).

[33] Eric Sabo, Arun B. Aloshious, and Kenneth R. Brown, "Trellis Decoding For Qudit Stabilizer Codes And Its Application To Qubit Topological Codes", arXiv:2106.08251, (2021).

[34] Anirudh Krishna and David Poulin, "Fault-tolerant gates on hypergraph product codes", arXiv:1909.07424, (2019).

[35] Nicolas Delfosse, Vivien Londe, and Michael Beverland, "Toward a Union-Find decoder for quantum LDPC codes", arXiv:2103.08049, (2021).

[36] Armanda O. Quintavalle and Earl T. Campbell, "ReShape: a decoder for hypergraph product codes", arXiv:2105.02370, (2021).

[37] Anqi Gong and Joseph M. Renes, "Improved Logical Error Rate via List Decoding of Quantum Polar Codes", arXiv:2304.04743, (2023).

[38] Nicolas Delfosse, Michael E. Beverland, and Maxime A. Tremblay, "Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes", arXiv:2109.14599, (2021).

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

[40] Nithin Raveendran and Bane Vasić, "Trapping Sets of Quantum LDPC Codes", Quantum 5, 562 (2021).

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

[42] Simon Burton and Dan Browne, "Limitations on transversal gates for hypergraph product codes", arXiv:2012.05842, (2020).

[43] Nicolas Delfosse and Matthew B. Hastings, "Union-Find Decoders For Homological Product Codes", Quantum 5, 406 (2021).

[44] Patricio Fuentes, Josu Etxezarreta Martinez, Pedro M. Crespo, and Javier Garcia-Frias, "On the logical error rate of sparse quantum codes", arXiv:2108.10645, (2021).

[45] Kao-Yueh Kuo and Ching-Yi Lai, "Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages", arXiv:2102.07122, (2021).

[46] Narayanan Rengaswamy, Ankur Raina, Nithin Raveendran, and Bane Vasić, "Distilling GHZ States using Stabilizer Codes", arXiv:2109.06248, (2021).

[47] Renyu Wang, Renyu Wang Team, and Leonid P. Pryadko Team, "Distance bounds for generalized bicycle codes", APS March Meeting Abstracts 2022, T40.003 (2022).

[48] Kao-Yueh Kuo and Ching-Yi Lai, "Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes", arXiv:2002.06502, (2020).

[49] 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 2023-06-08 17:22:27) and SAO/NASA ADS (last updated successfully 2023-06-08 17:22:27). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Degenerate Quantum LDPC Codes With Good Finite Length Performance

  1. Pingback: Perspective in Quantum Views by Joschka Roffe "Towards practical quantum LDPC codes"