Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Josias Old1,2 and Manuel Rispler1,2,3

1Institute for Quantum Information, RWTH Aachen University, Aachen, Germany
2Institute for Theoretical Nanoelectronics (PGI-2), Forschungszentrum Jülich, Jülich, Germany
3QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands

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

Abstract

Belief propagation (BP) is well-known as a low complexity decoding algorithm with a strong performance for important classes of quantum error correcting codes, e.g. notably for the quantum low-density parity check (LDPC) code class of random expander codes. However, it is also well-known that the performance of BP breaks down when facing topological codes such as the surface code, where naive BP fails entirely to reach a below-threshold regime, i.e. the regime where error correction becomes useful. Previous works have shown, that this can be remedied by resorting to post-processing decoders outside the framework of BP. In this work, we present a generalized belief propagation method with an outer re-initialization loop that successfully decodes surface codes, i.e. opposed to naive BP it recovers the sub-threshold regime known from decoders tailored to the surface code and from statistical-mechanical mappings. We report a threshold of $\textit{17%}$ under independent bit-and phase-flip data noise (to be compared to the ideal threshold of $\textit{20.6%}$) and a threshold value of $\textit{14%}$ under depolarizing data noise (compared to the ideal threshold of $\textit{18.9%}$), which are on par with thresholds achieved by non-BP post-processing methods.

Quantum computing devices suffer from operational errors and decoherence. Methods to keep errors in check and advance towards fault-tolerant quantum computing involve $\textit{quantum error correcting codes}$ and fast and accurate decoding algorithms. Belief propagation (BP) is well-known as a low complexity decoding algorithm with a strong performance for important classes of quantum error correcting codes, e.g. notably for the quantum low-density parity check (LDPC) code class of random expander codes. However, it is also well-known that the performance of BP breaks down when facing topological codes such as the surface code, where naive BP fails entirely to reach a below-threshold regime, i.e. the regime where error correction becomes useful. Previous works have shown, that this can be remedied by resorting to post-processing decoders outside the framework of BP. In this work, we present a generalized belief propagation method with an outer re-initialization loop that successfully decodes surface codes within the framework of BP, achieving a below-threshold regime.

► BibTeX data

► References

[1] Nikolas P. Breuckmann and Jens Niklas Eberhardt. ``Quantum Low-Density Parity-Check Codes''. PRX Quantum 2, 040101 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040101

[2] Daniel Gottesman. ``Fault-tolerant quantum computation with constant overhead''. Quantum Information & Computation 14, 1338–1372 (2014).
https:/​/​doi.org/​10.26421/​QIC14.15-16-5

[3] A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.1098

[4] Alexei Ashikhmin, Simon Litsyn, and Michael A Tsfasman. ``Asymptotically good quantum codes''. Physical Review A 63, 032311 (2001).
https:/​/​doi.org/​10.1103/​PhysRevA.63.032311

[5] Pavel Panteleev and Gleb Kalachev. ``Asymptotically good quantum and locally testable classical ldpc codes''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 375–388. (2022).
https:/​/​doi.org/​10.1145/​3519935.3520017

[6] Anthony Leverrier and Gilles Zémor. ``Quantum tanner codes''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 872–883. (2022).
https:/​/​doi.org/​10.1109/​FOCS54457.2022.00117

[7] Ting-Chun Lin and Min-Hsiu Hsieh. ``Good quantum ldpc codes with linear time decoder from lossless expanders'' (2022). arXiv:2203.03581.
arXiv:2203.03581

[8] David JC MacKay and Radford M Neal. ``Near shannon limit performance of low density parity check codes''. Electronics letters 33, 457–458 (1997).
https:/​/​doi.org/​10.1049/​el:19970362

[9] Nithin Raveendran and Bane Vasić . ``Trapping sets of quantum LDPC codes''. Quantum 5, 562 (2021).
https:/​/​doi.org/​10.22331/​q-2021-10-14-562

[10] Robert Raussendorf and Jim Harrington. ``Fault-Tolerant Quantum Computation with High Threshold in Two Dimensions''. Phys. Rev. Lett. 98, 190504 (2007).
https:/​/​doi.org/​10.1103/​PhysRevLett.98.190504

[11] Pavel Panteleev and Gleb Kalachev. ``Degenerate quantum LDPC codes with good finite length performance''. Quantum 5, 585 (2021).
https:/​/​doi.org/​10.22331/​q-2021-11-22-585

[12] Joschka Roffe, David R White, Simon Burton, and Earl Campbell. ``Decoding across the quantum low-density parity-check code landscape''. Physical Review Research 2, 043423 (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.043423

[13] Nithin Raveendran, Mohsen Bahrami, and Bane Vasic. ``Syndrome-generalized belief propagation decoding for quantum memories''. In ICC 2019 - 2019 IEEE International Conference on Communications (ICC). Pages 1–6. (2019).
https:/​/​doi.org/​10.1109/​ICC.2019.8761366

[14] E. Berlekamp, R. McEliece, and H. van Tilborg. ``On the inherent intractability of certain coding problems (corresp.)''. IEEE Transactions on Information Theory 24, 384–386 (1978).
https:/​/​doi.org/​10.1109/​TIT.1978.1055873

[15] Daniel Gottesman. ``Stabilizer codes and quantum error correction'' (1997). arXiv:quant-ph/​9705052.
arXiv:quant-ph/9705052

[16] R. 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

[17] Andrew Steane. ``Multiple-particle interference and quantum error correction''. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551–2577 (1996).
https:/​/​doi.org/​10.1098/​rspa.1996.0136

[18] M. Sipser and D. A. Spielman. ``Expander codes''. IEEE Transactions on Information Theory 42, 1710–1722 (1996).
https:/​/​doi.org/​10.1109/​18.556667

[19] David JC MacKay. ``Information theory, inference and learning algorithms''. Cambridge university press. (2003).

[20] A.Yu. Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

[21] J. Tillich and G. Zemor. ``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. (2009).
https:/​/​doi.org/​10.1109/​ISIT.2009.5205648

[22] A. Leverrier, J. Tillich, and G. Zémor. ``Quantum expander codes''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 810–824. (2015).
https:/​/​doi.org/​10.1109/​FOCS.2015.55

[23] Jonathan S Yedidia, William T Freeman, and Yair Weiss. ``Generalized belief propagation''. In NIPS. Volume 13, pages 689–695. (2000).

[24] Brendan J Frey, Frank R Kschischang, Hans-Andrea Loeliger, and Niclas Wiberg. ``Factor graphs and algorithms''. In Proceedings of the Annual Allerton Conference on Communication Control and Computing. Volume 35, pages 666–680. (1997).

[25] Max Welling. ``On the choice of regions for generalized belief propagation'' (2012). arXiv:1207.4158.
arXiv:1207.4158

[26] Vladimir Fanaskov. ``Gaussian belief propagation solvers for nonsymmetric systems of linear equations''. SIAM Journal on Scientific Computing 44, A77–A102 (2022).
https:/​/​doi.org/​10.1137/​19M1275139

[27] Jonathan S Yedidia, William T Freeman, and Yair Weiss. ``Constructing free-energy approximations and generalized belief propagation algorithms''. IEEE Transactions on information theory 51, 2282–2312 (2005).
https:/​/​doi.org/​10.1109/​TIT.2005.850085

[28] R. Gallager. ``Low-density parity-check codes''. IRE Transactions on Information Theory 8, 21–28 (1962).
https:/​/​doi.org/​10.1109/​TIT.1962.1057683

[29] Judea Pearl. ``Reverend bayes on inference engines: A distributed hierarchical approach''. In Proceedings of the Second AAAI Conference on Artificial Intelligence. Pages 133–136. AAAI'82. AAAI Press (1982).
https:/​/​doi.org/​10.1145/​3501714.3501727

[30] David Poulin and Yeojin Chung. ``On the iterative decoding of sparse quantum codes''. Quantum Information & Computation 8, 987–1000 (2008).
https:/​/​doi.org/​10.26421/​QIC8.10-8

[31] Alex Rigby, J. C. Olivier, and Peter Jarvis. ``Modified belief propagation decoders for quantum low-density parity-check codes''. Physical Review A 100 (2019).
https:/​/​doi.org/​10.1103/​physreva.100.012330

[32] Aiden Price and Joanne Hall. ``A survey on trapping sets and stopping sets'' (2017). arXiv:1705.05996.
arXiv:1705.05996

[33] Kao-Yueh Kuo and Ching-Yi Lai. ``Exploiting degeneracy in belief propagation decoding of quantum codes''. npj Quantum Information 8 (2022).
https:/​/​doi.org/​10.1038/​s41534-022-00623-2

[34] Manabu Hagiwara, Marc P. C. Fossorier, and Hideki Imai. ``Fixed initialization decoding of ldpc codes over a binary symmetric channel''. IEEE Transactions on Information Theory 58, 2321–2329 (2012).
https:/​/​doi.org/​10.1109/​TIT.2011.2177440

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

[36] H. Bombin, Ruben S. Andrist, Masayuki Ohzeki, Helmut G. Katzgraber, and M. A. Martin-Delgado. ``Strong resilience of topological codes to depolarization''. Phys. Rev. X 2, 021004 (2012).
https:/​/​doi.org/​10.1103/​PhysRevX.2.021004

[37] Vladimir Kolmogorov. ``Blossom v: a new implementation of a minimum cost perfect matching algorithm''. Mathematical Programming Computation 1, 43–67 (2009).
https:/​/​doi.org/​10.1007/​s12532-009-0002-8

[38] Nicolas Delfosse and Naomi H Nickerson. ``Almost-linear time decoding algorithm for topological codes''. Quantum 5, 595 (2021).
https:/​/​doi.org/​10.22331/​q-2021-12-02-595

[39] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier. ``Combining hard and soft decoders for hypergraph product codes''. Quantum 5, 432 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-15-432

[40] Armanda O Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T Campbell. ``Single-shot error correction of three-dimensional homological product codes''. PRX Quantum 2, 020340 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.020340

[41] Joris M. Mooij. ``Libdai: A free and open source c++ library for discrete approximate inference in graphical models''. J. Mach. Learn. Res. 11, 2169–2173 (2010).

[42] Balázs Dezső, Alpár Jüttner, and Péter Kovács. ``Lemon – an open source c++ graph template library''. Electronic Notes in Theoretical Computer Science 264, 23–45 (2011).
https:/​/​doi.org/​10.1016/​j.entcs.2011.06.003

[43] Johan Mabille, Sylvain Corlay, and Wolf Vollprecht (2016). code: xtensor-stack/​xtensor.
https:/​/​github.com/​xtensor-stack/​xtensor

[44] Victor Shoup. ``Ntl: A library for doing number theory''. (2021). url: https:/​/​libntl.org. code: libntl/​ntl.
https:/​/​libntl.org

[45] Niels Lohmann (2022). code: nlohmann v3.10.5.
https:/​/​github.com/​nlohmann

[46] Josias Old (2022). code: josiasold/​gbp.
https:/​/​github.com/​josiasold/​gbp

Cited by

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

[2] Christopher A. Pattison, Anirudh Krishna, and John Preskill, "Hierarchical memories: Simulating quantum LDPC codes with local gates", arXiv:2303.04798, (2023).

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

[4] Laura Caune, Brendan Reid, Joan Camps, and Earl Campbell, "Belief propagation as a partial decoder", arXiv:2306.17142, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 09:23:57) and SAO/NASA ADS (last updated successfully 2024-03-28 09:23:58). The list may be incomplete as not all publishers provide suitable and complete citation data.