Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Josias Old; Manuel Rispler

doi:10.22331/q-2023-06-07-1037

Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Josias Old^1,2 and Manuel Rispler^1,2,3

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

Published:	2023-06-07, volume 7, page 1037
Eprint:	arXiv:2212.03214v2
Doi:	https://doi.org/10.22331/q-2023-06-07-1037
Citation:	Quantum 7, 1037 (2023).

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.

Popular summary

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

@article{Old2023generalizedbelief,
  doi = {10.22331/q-2023-06-07-1037},
  url = {https://doi.org/10.22331/q-2023-06-07-1037},
  title = {Generalized {B}elief {P}ropagation {A}lgorithms for {D}ecoding of {S}urface {C}odes},
  author = {Old, Josias and Rispler, Manuel},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1037},
  month = jun,
  year = {2023}
}

► 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] Masoumeh Alinia, David G. M. Mitchell, Hanwen Yao, and Henry D. Pfister, 2025 13th International Symposium on Topics in Coding (ISTC) 1 (2025) ISBN:979-8-3315-8983-7.

[2] Siddhant Midha and Yifan F. Zhang, "Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence", PRX Quantum 7 3, 033010 (2026).

[3] Daniel Bascones, Francisco Garcia-Herrero, and Javier Valls, "Exploring the FPGA and ASIC design space of belief propagation and ordered statistics decoders for Quantum Error Correction Codes", (2025).

[4] Robert Joo, "Decoding the surface code with a spatio-temporal transformer", EPJ Quantum Technology 13 1, 52 (2026).

[5] Avimita Chatterjee and Swaroop Ghosh, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 356 (2024) ISBN:979-8-3315-4137-8.

[6] Jiahan Chen, Zhengzhong Yi, Zhipeng Liang, and Xuan Wang, "Improved Belief Propagation Decoding Algorithms for Surface Codes", IEEE Transactions on Quantum Engineering 6, 1 (2025).

[7] Arshpreet Singh Maan and Alexandru Paler, "Machine learning message-passing for the scalable decoding of QLDPC codes", npj Quantum Information 11 1, 78 (2025).

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

[9] Xueqiao Wang, Chenhao Huang, and Xingkui Fan, "From Local Correction to Global Logical Verification: Two-Stage Machine Learning Decoding for Surface Codes", Applied Sciences 16 11, 5409 (2026).

[10] Xingyu Qiao, Xiaoxuan Xu, Hongyang Ma, and Tianhui Qiu, "Fault-Tolerant Hybrid Decoder for Quantum Surface Codes on Probabilistic Inference and Topological Clustering", Applied Sciences 16 5, 2586 (2026).

[11] Sana Javed, Sergio Colet, Francisco Garcia-Herrero, Óscar Ruano, Juan Antonio Maestro, Bane Vasić, and Mark F. Flanagan, "Low-Complexity Syndrome-Based Linear Programming Decoding of Quantum LDPC Codes", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[12] Julien Du Crest, Mehdi Mhalla, and Valentin Savin, "A Blindness Property of the Min-Sum Decoding for the Toric Code", IEEE Journal on Selected Areas in Information Theory 6, 138 (2025).

[13] Qianfan Wang, Jifan Liang, Lvzhou Li, Linqi Song, and Xiao Ma, "BP-LCGCD: A Gaussian-Elimination-Free and High-Performance Decoder for Surface Codes", IEEE Communications Letters 30, 782 (2026).

[14] Raffaele Marino, Lorenzo Buffoni, and Bogdan Zavalnij, "A short review on the maximum clique problem algorithms with classical, AI, and quantum methods", Communications Physics 9 1, 239 (2026).

[15] Christopher A. Pattison, Anirudh Krishna, and John Preskill, "Hierarchical memories: Simulating quantum LDPC codes with local gates", Quantum 9, 1728 (2025).

[16] Jifan Liang, Qianfan Wang, Lvzhou Li, and Xiao Ma, 2024 IEEE International Symposium on Information Theory Workshops (ISIT-W) 1 (2024) ISBN:979-8-3503-4844-6.

[17] Kaiwen Zhou, Liqiang Lu, Debin Xiang, Chenning Tao, Anbang Wu, Jingwen Leng, Fangxin Liu, Mingshuai Chen, and Jianwei Yin, Proceedings of the 58th IEEE/ACM International Symposium on Microarchitecture 719 (2025) ISBN:9798400715730.

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

[19] Ahmed Adel Mahmoud, Kamal Mohamed Ali, and Steven Rayan, "Systematic approach to hyperbolic quantum error correction codes", Physical Review A 113 4, 042426 (2026).

[20] Boqing Zhang, Hanwen Yao, and Henry D. Pfister, 2025 IEEE International Symposium on Information Theory (ISIT) 1 (2025) ISBN:979-8-3315-4399-0.

[21] Marzio Vallero, Gioele Casagranda, Flavio Vella, and Paolo Rech, SC24: International Conference for High Performance Computing, Networking, Storage and Analysis 1 (2024) ISBN:979-8-3503-5291-7.

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

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

[24] Marzio Vallero, Gioele Casagranda, Flavio Vella, and Paolo Rech, "On the Efficacy of Surface Codes in Compensating for Radiation Events in Superconducting Devices", arXiv:2407.10841, (2024).

[25] Xiangjun Mi and Frank Mueller, "Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes", arXiv:2510.06257, (2025).

[26] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-12 19:15:34) and SAO/NASA ADS (last updated successfully 2026-08-12 19:15:36). 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.