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.


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

[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] Naomi H. Nickerson and Benjamin J. Brown, "Analysing correlated noise on the surface code using adaptive decoding algorithms", Quantum 3, 131 (2019).

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

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

[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] 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", arXiv:1705.07855, Quantum 2, 48 (2018).

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

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

[12] Christophe Piveteau and Joseph M. Renes, "Quantum message-passing algorithm for optimal and efficient decoding", arXiv:2109.08170.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-20 06:08:12) and SAO/NASA ADS (last updated successfully 2021-10-20 06:08:13). The list may be incomplete as not all publishers provide suitable and complete citation data.