Multi-path Summation for Decoding 2D Topological Codes

Ben Criger1,2 and Imran Ashraf1

1QuTech, TU Delft
2Institute for Globally Distributed Open Research and Education (IGDORE)

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

Updated version: The authors have uploaded version v6 of this work to the arXiv which may contain updates or corrections not contained in the published version v5. The authors left the following comment on the arXiv:
19 pages, 13 figures, published in Quantum, available at this https URL


Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of $17.76 \pm 0.02 \%$. This is larger than the threshold achieved by previous matching-based decoders ($14.88 \pm 0.02 \%$), though still below the known upper bound of $\sim 18.9 \%$.

► BibTeX data

► References

[1] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, 1997. 10.1137/​S0097539795293172. URL http:/​/​​10.1137/​S0097539795293172.

[2] I. M. Georgescu, S. Ashhab, and Franco Nori. Quantum simulation. Rev. Mod. Phys., 86: 153–185, Mar 2014. 10.1103/​RevModPhys.86.153. URL https:/​/​​10.1103/​revmodphys.86.153.

[3] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. Caltech Ph.D. Thesis, 1997. 10.7907/​rzr7-dt72. URL https:/​/​​10.7907/​rzr7-dt72.

[4] A. M. Steane. Active stabilization, quantum computation, and quantum state synthesis. Phys. Rev. Lett., 78: 2252–2255, Mar 1997. 10.1103/​PhysRevLett.78.2252. URL https:/​/​​10.1103/​physrevlett.78.2252.

[5] Emanuel Knill and Raymond Laflamme. Theory of quantum error-correcting codes. Phys. Rev. A, 55: 900–911, Feb 1997. 10.1103/​PhysRevA.55.900. URL https:/​/​​10.1103/​physreva.55.900.

[6] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, 2nd edition, 1978. ISBN 9780080570877. URL https:/​/​​books/​the-theory-of-error-correcting-codes/​macwilliams/​978-0-444-85193-2.

[7] Daniel A. Lidar and Todd A. Brun. Quantum Error Correction. Cambridge University Press, 2013. 10.1017/​CBO9781139034807. URL https:/​/​​10.1017/​CBO9781139034807.

[8] A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2 – 30, 2003. ISSN 0003-4916. 10.1016/​s0003-4916(02)00018-0. URL https:/​/​​10.1016/​s0003-4916(02)00018-0.

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

[10] Sergey B. Bravyi and A. Yu. Kitaev. Quantum codes on a lattice with boundary. arXiv preprint quant-ph/​9811052, 1998. URL https:/​/​​abs/​quant-ph/​9811052.

[11] H. Bombin and M. A. Martin-Delgado. Optimal resources for topological two-dimensional stabilizer codes: Comparative study. Physical Review A, 76 (1), jul 2007. 10.1103/​physreva.76.012305. URL https:/​/​​10.1103.

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

[13] D.S. Wang, A.G. Fowler, A.M. Stephens, and L.C.L. Hollenberg. Threshold error rates for the toric and planar codes. Quantum Information & Computation, 10 (5): 456–469, 2010. 10.26421/​QIC10.5. URL https:/​/​​10.26421/​QIC10.5.

[14] Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17: 449–467, 1965. 10.4153/​CJM-1965-045-4. URL http:/​/​​10.4153/​CJM-1965-045-4.

[15] Vladimir Kolmogorov. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1: 43–67, 2009. 10.1007/​s12532-009-0002-8. URL http:/​/​​10.1007/​s12532-009-0002-8.

[16] Chenyang Wang, Jim Harrington, and John Preskill. Confinement-higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory. Annals of Physics, 303 (1): 31–58, jan 2003. 10.1016/​s0003-4916(02)00019-2. URL https:/​/​​10.1016.

[17] F. Merz and J. T. Chalker. Two-dimensional random-bond ising model, free fermions, and the network model. Physical Review B, 65 (5), jan 2002. 10.1103/​physrevb.65.054425. URL https:/​/​​10.1103.

[18] A. Honecker, M. Picco, and P. Pujol. Universality class of the nishimori point in the 2d$\pm$JRandom-bond ising model. Physical Review Letters, 87 (4), jul 2001. 10.1103/​physrevlett.87.047201. URL https:/​/​​10.1103.

[19] Nicolas Delfosse and Jean-Pierre Tillich. A decoding algorithm for CSS codes using the $X$/​$Z$ correlations. In 2014 IEEE International Symposium on Information Theory. IEEE, jun 2014. 10.1109/​isit.2014.6874997. URL https:/​/​​10.1109.

[20] Austin G. Fowler. Optimal complexity correction of correlated errors in the surface code. arXiv preprint arXiv:1310.0863, 2013a. URL https:/​/​​abs/​1310.0863.

[21] Thomas M. Stace, Sean D. Barrett, and Andrew C. Doherty. Thresholds for topological codes in the presence of loss. Physical Review Letters, 102 (20), may 2009. 10.1103/​physrevlett.102.200501. URL https:/​/​​10.1103.

[22] Sean D. Barrett and Thomas M. Stace. Fault tolerant quantum computation with very high threshold for loss errors. Physical Review Letters, 105 (20), nov 2010. 10.1103/​physrevlett.105.200502. URL https:/​/​​10.1103.

[23] Thomas M. Stace and Sean D. Barrett. Error correction and degeneracy in surface codes suffering loss. Physical Review A, 81 (2), feb 2010. 10.1103/​physreva.81.022317. URL https:/​/​​10.1103.

[24] Project Euler: Problem 15. https:/​/​​problem=15. Accessed: 2017-08-07.

[25] H Freund and P Grassberger. The ground state of the $+$ or $-$ $J$ spin glass from a heuristic matching algorithm. Journal of Physics A: Mathematical and General, 22 (18): 4045–4059, sep 1989. 10.1088/​0305-4470/​22/​18/​036. URL https:/​/​​10.1088.

[26] Adrian Hutter, James R. Wootton, and Daniel Loss. Efficient markov chain monte carlo algorithm for the surface code. Physical Review A, 89 (2): 022326, feb 2014. 10.1103/​physreva.89.022326. URL https:/​/​​10.1103.

[27] Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum likelihood decoding in the surface code. Physical Review A, 90 (3), sep 2014. 10.1103/​physreva.90.032326. URL https:/​/​​10.1103.

[28] Guillaume Duclos-Cianci and David Poulin. A renormalization group decoding algorithm for topological quantum codes. In 2010 IEEE Information Theory Workshop. IEEE, aug 2010a. 10.1109/​cig.2010.5592866. URL https:/​/​​10.1109.

[29] Leslie G. Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31 (4): 1229–1254, jan 2002. 10.1137/​s0097539700377025. URL https:/​/​​10.1137.

[30] Sergey Bravyi. Lagrangian representation for fermionic linear optics. Quantum Information & Computation, 5 (3): 216–238, 2005. 10.26421/​QIC5.3. URL https:/​/​​10.26421/​QIC5.3.

[31] Guifré Vidal. Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters, 91 (14), oct 2003. 10.1103/​physrevlett.91.147902. URL https:/​/​​10.1103.

[32] Guillaume Duclos-Cianci and David Poulin. A renormalization group decoding algorithm for topological quantum codes. Information Theory Workshop (ITW), IEEE, pages 1 – 5, 2010b. 10.1109/​CIG.2010.5592866. URL http:/​/​​10.1109/​CIG.2010.5592866.

[33] Adrian Hutter, Daniel Loss, and James R Wootton. Improved HDRG decoders for qudit and non-abelian quantum error correction. New Journal of Physics, 17 (3): 035017, mar 2015. 10.1088/​1367-2630/​17/​3/​035017. URL https:/​/​​10.1088.

[34] D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. ISBN 9780521642989. URL https:/​/​​books?id=AKuMj4PN_EMC.

[35] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. Computer science. MIT Press, 2009. ISBN 9780262533058. URL https:/​/​​books?id=aefUBQAAQBAJ.

[36] Ashley M. Stephens. Fault-tolerant thresholds for quantum error correction with the surface code. Physical Review A, 89 (2), feb 2014. 10.1103/​physreva.89.022321. URL https:/​/​​10.1103.

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

[38] S. Flammia. personal communication, 2017.

[39] Austin G. Fowler. Accurate simulations of planar topological codes cannot use cyclic boundaries. Physical Review A, 87 (6), jun 2013b. 10.1103/​physreva.87.062320. URL https:/​/​​10.1103.

[40] David K. Tuckett, Stephen D. Bartlett, and Steven T. Flammia. Ultrahigh error threshold for surface codes with biased noise. Physical Review Letters, 120 (5), jan 2018. 10.1103/​physrevlett.120.050505. URL https:/​/​​10.1103.

[41] Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg. Towards practical classical processing for the surface code. Physical Review Letters, 108 (18), may 2012. 10.1103/​physrevlett.108.180501. URL https:/​/​​10.1103.

[42] Nicolas Delfosse. Decoding color codes by projection onto surface codes. Physical Review A, 89 (1), jan 2014. 10.1103/​physreva.89.012317. URL https:/​/​​10.1103.

[43] Stéfan van der Walt, S Chris Colbert, and Gaël Varoquaux. The NumPy array: A structure for efficient numerical computation. Computing in Science & Engineering, 13 (2): 22–30, mar 2011. 10.1109/​mcse.2011.37. URL https:/​/​​10.1109.

[44] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 – 15, Pasadena, CA USA, 2008. URL https:/​/​​.

[45] Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python, 2001–. URL https:/​/​​. [Online; accessed 2017-09-01].

[46] John D. Hunter. Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9 (3): 90–95, 2007. 10.1109/​mcse.2007.55. URL https:/​/​​10.1109.

[47] Seaborn: statistical data visualization. https:/​/​​. Accessed: 2017-09-01.

[48] Daniel Foreman-Mackey, David W. Hogg, Dustin Lang, and Jonathan Goodman. emcee: The MCMC hammer. Publications of the Astronomical Society of the Pacific, 125 (925): 306–312, mar 2013. 10.1086/​670067. URL https:/​/​​10.1086.

[49] sc_decoding. https:/​/​​bcriger/​sc_decoding.

Cited by

[1] Poulami Das, Christopher A. Pattison, Srilatha Manne, Douglas M. Carmean, Krysta M. Svore, Moinuddin Qureshi, and Nicolas Delfosse, 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA) 259 (2022) ISBN:978-1-6654-2027-3.

[2] Nishad Maskara, Aleksander Kubica, and Tomas Jochym-O'Connor, "Advantages of versatile neural-network decoding for topological codes", Physical Review A 99 5, 052351 (2019).

[3] Benjamin J. Brown and Dominic J. Williamson, "Parallelized quantum error correction with fracton topological codes", Physical Review Research 2 1, 013303 (2020).

[4] Michael E Beverland, Benjamin J Brown, Michael J Kastoryano, and Quentin Marolleau, "The role of entropy in topological quantum error correction", Journal of Statistical Mechanics: Theory and Experiment 2019 7, 073404 (2019).

[5] Patricio Fuentes, Josu Etxezarreta Martinez, Pedro M. Crespo, and Javier Garcia-Frias, "Approach for the construction of non-Calderbank-Steane-Shor low-density-generator-matrix–based quantum codes", Physical Review A 102 1, 012423 (2020).

[6] Jing Hao Chai and Hui Khoon Ng, "On the Fault‐Tolerance Threshold for Surface Codes with General Noise", Advanced Quantum Technologies 5 10, 2200008 (2022).

[7] F Battistel, C Chamberland, K Johar, R W J Overwater, F Sebastiano, L Skoric, Y Ueno, and M Usman, "Real-time decoding for fault-tolerant quantum computing: progress, challenges and outlook", Nano Futures 7 3, 032003 (2023).

[8] Georgia M. Nixon and Benjamin J. Brown, "Correcting Spanning Errors With a Fractal Code", IEEE Transactions on Information Theory 67 7, 4504 (2021).

[9] Tim Chan and Simon C. Benjamin, "Actis: A Strictly Local Union–Find Decoder", Quantum 7, 1183 (2023).

[10] Konstantin Tiurev, Peter-Jan H. S. Derks, Joschka Roffe, Jens Eisert, and Jan-Michael Reiner, "Correcting non-independent and non-identically distributed errors with surface codes", Quantum 7, 1123 (2023).

[11] Jun Fujisaki, Kazunori Maruyama, Hirotaka Oshima, Shintaro Sato, Tatsuya Sakashita, Yusaku Takeuchi, and Keisuke Fujii, "Quantum error correction with an Ising machine under circuit-level noise", Physical Review Research 5 4, 043261 (2023).

[12] Paul Baireuther, Thomas E. O'Brien, Brian Tarasinski, and Carlo W. J. Beenakker, "Machine-learning-assisted correction of correlated qubit errors in a topological code", Quantum 2, 48 (2018).

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

[14] Pei-Kai Tsai, Yue Wu, and Shruti Puri, "Mitigating Temporal Fragility in the XY Surface Code", Physical Review X 14 3, 031003 (2024).

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

[16] Karl Hammar, Alexei Orekhov, Patrik Wallin Hybelius, Anna Katariina Wisakanto, Basudha Srivastava, Anton Frisk Kockum, and Mats Granath, "Error-rate-agnostic decoding of topological stabilizer codes", Physical Review A 105 4, 042616 (2022).

[17] Naomi H. Nickerson and Benjamin J. Brown, "Analysing correlated noise on the surface code using adaptive decoding algorithms", Quantum 3, 131 (2019).

[18] Joschka Roffe, "Quantum error correction: an introductory guide", Contemporary Physics 60 3, 226 (2019).

[19] Rajeev Acharya, Igor Aleiner, Richard Allen, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Joao Basso, Andreas Bengtsson, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Dripto M. Debroy, Alexander Del Toro Barba, Sean Demura, Andrew Dunsworth, Daniel Eppens, Catherine Erickson, Lara Faoro, Edward Farhi, Reza Fatemi, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, William Giang, Craig Gidney, Dar Gilboa, Marissa Giustina, Alejandro Grajales Dau, Jonathan A. Gross, Steve Habegger, Michael C. Hamilton, Matthew P. Harrigan, Sean D. Harrington, Oscar Higgott, Jeremy Hilton, Markus Hoffmann, Sabrina Hong, Trent Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Pavol Juhas, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Tanuj Khattar, Mostafa Khezri, Mária Kieferová, Seon Kim, Alexei Kitaev, Paul V. Klimov, Andrey R. Klots, Alexander N. Korotkov, Fedor Kostritsa, John Mark Kreikebaum, David Landhuis, Pavel Laptev, Kim-Ming Lau, Lily Laws, Joonho Lee, Kenny Lee, Brian J. Lester, Alexander Lill, Wayne Liu, Aditya Locharla, Erik Lucero, Fionn D. Malone, Jeffrey Marshall, Orion Martin, Jarrod R. McClean, Trevor McCourt, Matt McEwen, Anthony Megrant, Bernardo Meurer Costa, Xiao Mi, Kevin C. Miao, Masoud Mohseni, Shirin Montazeri, Alexis Morvan, Emily Mount, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Murphy Yuezhen Niu, Thomas E. O’Brien, Alex Opremcak, John Platt, Andre Petukhov, Rebecca Potter, Leonid P. Pryadko, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Michael J. Shearn, Aaron Shorter, Vladimir Shvarts, Jindra Skruzny, Vadim Smelyanskiy, W. Clarke Smith, George Sterling, Doug Strain, Marco Szalay, Alfredo Torres, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Theodore White, Cheng Xing, Z. Jamie Yao, Ping Yeh, Juhwan Yoo, Grayson Young, Adam Zalcman, Yaxing Zhang, and Ningfeng Zhu, "Suppressing quantum errors by scaling a surface code logical qubit", Nature 614 7949, 676 (2023).

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

[21] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell, "Improved Decoding of Circuit Noise and Fragile Boundaries of Tailored Surface Codes", Physical Review X 13 3, 031007 (2023).

[22] Basudha Srivastava, Anton Frisk Kockum, and Mats Granath, "The XYZ2 hexagonal stabilizer code", Quantum 6, 698 (2022).

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

[24] Christopher T. Chubb and Steven T. Flammia, "Statistical mechanical models for quantum codes with correlated noise", Annales de l'Institut Henri Poincare D 8 2, 269 (2021).

[25] Christopher T. Chubb, "General tensor network decoding of 2D Pauli codes", arXiv:2101.04125, (2021).

[26] Wang Fang and Mingsheng Ying, "Symbolic Execution for Quantum Error Correction Programs", arXiv:2311.11313, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 16:41:48) and SAO/NASA ADS (last updated successfully 2024-07-15 16:41:49). The list may be incomplete as not all publishers provide suitable and complete citation data.