{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T12:39:41Z","timestamp":1794055181377,"version":"4.8.0"},"reference-count":46,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"EU Quantum Technology Flagship","award":["AQTION\/820495"],"award-info":[{"award-number":["AQTION\/820495"]}]},{"name":"BMBF","award":["MUNIQC-ATOMS"],"award-info":[{"award-number":["MUNIQC-ATOMS"]}]},{"name":"European Research Council","award":["ERC\/682726"],"award-info":[{"award-number":["ERC\/682726"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 17%<\/mml:mtext><\/mml:mrow><\/mml:math> under independent bit-and phase-flip data noise (to be compared to the ideal threshold of 20.6%<\/mml:mtext><\/mml:mrow><\/mml:math>) and a threshold value of 14%<\/mml:mtext><\/mml:mrow><\/mml:math> under depolarizing data noise (compared to the ideal threshold of 18.9%<\/mml:mtext><\/mml:mrow><\/mml:math>), which are on par with thresholds achieved by non-BP post-processing methods.<\/jats:p>","DOI":"10.22331\/q-2023-06-07-1037","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T10:53:02Z","timestamp":1686135182000},"page":"1037","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":23,"title":["Generalized Belief Propagation Algorithms for Decoding of Surface Codes"],"prefix":"10.22331","volume":"7","author":[{"given":"Josias","family":"Old","sequence":"first","affiliation":[{"name":"Institute for Quantum Information, RWTH Aachen University, Aachen, Germany"},{"name":"Institute for Theoretical Nanoelectronics (PGI-2), Forschungszentrum J\u00fclich, J\u00fclich, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manuel","family":"Rispler","sequence":"additional","affiliation":[{"name":"Institute for Quantum Information, RWTH Aachen University, Aachen, Germany"},{"name":"Institute for Theoretical Nanoelectronics (PGI-2), Forschungszentrum J\u00fclich, J\u00fclich, Germany"},{"name":"QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Nikolas P. Breuckmann and Jens Niklas Eberhardt. ``Quantum Low-Density Parity-Check Codes''. PRX Quantum 2, 040101 (2021).","DOI":"10.1103\/PRXQuantum.2.040101"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. ``Fault-tolerant quantum computation with constant overhead''. Quantum Information & Computation 14, 1338\u20131372 (2014).","DOI":"10.26421\/QIC14.15-16-5"},{"key":"2","doi-asserted-by":"publisher","unstructured":"A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).","DOI":"10.1103\/PhysRevA.54.1098"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Alexei Ashikhmin, Simon Litsyn, and Michael A Tsfasman. ``Asymptotically good quantum codes''. Physical Review A 63, 032311 (2001).","DOI":"10.1103\/PhysRevA.63.032311"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u2013388. (2022).","DOI":"10.1145\/3519935.3520017"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Anthony Leverrier and Gilles Z\u00e9mor. ``Quantum tanner codes''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 872\u2013883. (2022).","DOI":"10.1109\/FOCS54457.2022.00117"},{"key":"6","unstructured":"Ting-Chun Lin and Min-Hsiu Hsieh. ``Good quantum ldpc codes with linear time decoder from lossless expanders'' (2022). arXiv:2203.03581."},{"key":"7","doi-asserted-by":"publisher","unstructured":"David JC MacKay and Radford M Neal. ``Near shannon limit performance of low density parity check codes''. Electronics letters 33, 457\u2013458 (1997).","DOI":"10.1049\/el:19970362"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Nithin Raveendran and Bane Vasi\u0107 . ``Trapping sets of quantum LDPC codes''. Quantum 5, 562 (2021).","DOI":"10.22331\/q-2021-10-14-562"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Robert Raussendorf and Jim Harrington. ``Fault-Tolerant Quantum Computation with High Threshold in Two Dimensions''. Phys. Rev. Lett. 98, 190504 (2007).","DOI":"10.1103\/PhysRevLett.98.190504"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Pavel Panteleev and Gleb Kalachev. ``Degenerate quantum LDPC codes with good finite length performance''. Quantum 5, 585 (2021).","DOI":"10.22331\/q-2021-11-22-585"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevResearch.2.043423"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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\u20136. (2019).","DOI":"10.1109\/ICC.2019.8761366"},{"key":"13","doi-asserted-by":"publisher","unstructured":"E. Berlekamp, R. McEliece, and H. van Tilborg. ``On the inherent intractability of certain coding problems (corresp.)''. IEEE Transactions on Information Theory 24, 384\u2013386 (1978).","DOI":"10.1109\/TIT.1978.1055873"},{"key":"14","unstructured":"Daniel Gottesman. ``Stabilizer codes and quantum error correction'' (1997). arXiv:quant-ph\/9705052."},{"key":"15","doi-asserted-by":"publisher","unstructured":"R. Tanner. ``A recursive approach to low complexity codes''. IEEE Transactions on Information Theory 27, 533\u2013547 (1981).","DOI":"10.1109\/TIT.1981.1056404"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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\u20132577 (1996).","DOI":"10.1098\/rspa.1996.0136"},{"key":"17","doi-asserted-by":"publisher","unstructured":"M. Sipser and D. A. Spielman. ``Expander codes''. IEEE Transactions on Information Theory 42, 1710\u20131722 (1996).","DOI":"10.1109\/18.556667"},{"key":"18","unstructured":"David JC MacKay. ``Information theory, inference and learning algorithms''. Cambridge university press. (2003)."},{"key":"19","doi-asserted-by":"publisher","unstructured":"A.Yu. Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of Physics 303, 2\u201330 (2003).","DOI":"10.1016\/S0003-4916(02)00018-0"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u2013803. (2009).","DOI":"10.1109\/ISIT.2009.5205648"},{"key":"21","doi-asserted-by":"publisher","unstructured":"A. Leverrier, J. Tillich, and G. Z\u00e9mor. ``Quantum expander codes''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 810\u2013824. (2015).","DOI":"10.1109\/FOCS.2015.55"},{"key":"22","unstructured":"Jonathan S Yedidia, William T Freeman, and Yair Weiss. ``Generalized belief propagation''. In NIPS. Volume 13, pages 689\u2013695. (2000)."},{"key":"23","unstructured":"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\u2013680. (1997)."},{"key":"24","unstructured":"Max Welling. ``On the choice of regions for generalized belief propagation'' (2012). arXiv:1207.4158."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Vladimir Fanaskov. ``Gaussian belief propagation solvers for nonsymmetric systems of linear equations''. SIAM Journal on Scientific Computing 44, A77\u2013A102 (2022).","DOI":"10.1137\/19M1275139"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u20132312 (2005).","DOI":"10.1109\/TIT.2005.850085"},{"key":"27","doi-asserted-by":"publisher","unstructured":"R. Gallager. ``Low-density parity-check codes''. IRE Transactions on Information Theory 8, 21\u201328 (1962).","DOI":"10.1109\/TIT.1962.1057683"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Judea Pearl. ``Reverend bayes on inference engines: A distributed hierarchical approach''. In Proceedings of the Second AAAI Conference on Artificial Intelligence. Pages 133\u2013136. AAAI'82. AAAI Press (1982).","DOI":"10.1145\/3501714.3501727"},{"key":"29","doi-asserted-by":"publisher","unstructured":"David Poulin and Yeojin Chung. ``On the iterative decoding of sparse quantum codes''. Quantum Information & Computation 8, 987\u20131000 (2008).","DOI":"10.26421\/QIC8.10-8"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Alex Rigby, J. C. Olivier, and Peter Jarvis. ``Modified belief propagation decoders for quantum low-density parity-check codes''. Physical Review A 100 (2019).","DOI":"10.1103\/physreva.100.012330"},{"key":"31","unstructured":"Aiden Price and Joanne Hall. ``A survey on trapping sets and stopping sets'' (2017). arXiv:1705.05996."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Kao-Yueh Kuo and Ching-Yi Lai. ``Exploiting degeneracy in belief propagation decoding of quantum codes''. npj Quantum Information 8 (2022).","DOI":"10.1038\/s41534-022-00623-2"},{"key":"33","doi-asserted-by":"publisher","unstructured":"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\u20132329 (2012).","DOI":"10.1109\/TIT.2011.2177440"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452\u20134505 (2002).","DOI":"10.1063\/1.1499754"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevX.2.021004"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Vladimir Kolmogorov. ``Blossom v: a new implementation of a minimum cost perfect matching algorithm''. Mathematical Programming Computation 1, 43\u201367 (2009).","DOI":"10.1007\/s12532-009-0002-8"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Nicolas Delfosse and Naomi H Nickerson. ``Almost-linear time decoding algorithm for topological codes''. Quantum 5, 595 (2021).","DOI":"10.22331\/q-2021-12-02-595"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Antoine Grospellier, Lucien Grou\u00e8s, Anirudh Krishna, and Anthony Leverrier. ``Combining hard and soft decoders for hypergraph product codes''. Quantum 5, 432 (2021).","DOI":"10.22331\/q-2021-04-15-432"},{"key":"39","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.2.020340"},{"key":"40","unstructured":"Joris M. Mooij. ``Libdai: A free and open source c++ library for discrete approximate inference in graphical models''. J. Mach. Learn. Res. 11, 2169\u20132173 (2010)."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Bal\u00e1zs Dezs\u0151, Alp\u00e1r J\u00fcttner, and P\u00e9ter Kov\u00e1cs. ``Lemon \u2013 an open source c++ graph template library''. Electronic Notes in Theoretical Computer Science 264, 23\u201345 (2011).","DOI":"10.1016\/j.entcs.2011.06.003"},{"key":"42","unstructured":"Johan Mabille, Sylvain Corlay, and Wolf Vollprecht (2016). code: xtensor-stack\/xtensor."},{"key":"43","unstructured":"Victor Shoup. ``Ntl: A library for doing number theory''. (2021). url: https:\/\/libntl.org. code: libntl\/ntl."},{"key":"44","unstructured":"Niels Lohmann (2022). code: nlohmann v3.10.5."},{"key":"45","unstructured":"Josias Old (2022). code: josiasold\/gbp."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-06-07-1037\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T10:53:16Z","timestamp":1686135196000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-06-07-1037\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":46,"URL":"https:\/\/doi.org\/10.22331\/q-2023-06-07-1037","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"article-number":"1037"}}