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

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}<br /> }

► 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] Joschka Roffe, Lawrence Z. Cohen, Armanda O. Quintavalle, Daryus Chandra, and Earl T. Campbell, “Bias-tailored quantum LDPC codes”, Quantum 7, 1005 (2023).

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-06-07 10:47:23). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-06-07 10:47:21: Could not fetch cited-by data for 10.22331/q-2023-06-07-1037 from Crossref. This is normal if the DOI was registered recently.

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.

Plato Data Intelligence.
Vertical Search & Ai.

Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Abstract

Popular summary

► BibTeX data

► References

Cited by

Taiwan’s ACE Exchange Founder and Associates Face 20-Year Prison Sentences in Fraud and Money Laundering Case

DOJ insists Tornado Cash operated as a ‘commercial enterprise’

Latest Intelligence

Young Investor Skyrockets Initial $500 To $20,000 In Under One Week With Emerging Competitor To Shiba Inu (SHIB) – CryptoInfoNet

CoinGecko Reports NFT Lending Surpasses $2.1 Billion In Q1, Reaching A Quarterly High – CryptoInfoNet

5 Altcoins You Should Keep An Eye On In May

XRP, Ether, Cardano, SOL, Shiba Inu to Activate New Price Explosions as Key Metrics Suggest Crypto Winter is Over

Meow Scientist (MEOWSC) to Rally 6,500%, Looks to Challenge Shiba Inu and Dogecoin

Yuga Labs announces restructuring in push towards ‘Otherside’ metaverse development

Chat with us

Plato Data Intelligence.Vertical Search & Ai.

Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Abstract

Cited by

Latest Intelligence

Chat with us

Plato Data Intelligence.
Vertical Search & Ai.