CoChat

Multi-path Summation for Decoding 2D Topological Codes

Open access
Criger, Ben, Ashraf, Imran · 2018 · Quantum
Cited by 45

The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.

Abstract

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±0.02%. This is larger than the threshold achieved by previous matching-based decoders (14.88±0.02%), though still below the known upper bound of ∼18.9%.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.22331/q-2018-10-19-102

Cites

14 of 14 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 31

  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://dx.doi.org/10.1137/S0097539795293172. · DOI · Paper page
  2. Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. Caltech Ph.D. Thesis, 1997. 10.7907/rzr7-dt72. URL https://doi.org/10.7907/rzr7-dt72. · doi:10.7907/rzr7-dt72 · Paper page
  3. 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://doi.org/10.1103/physrevlett.78.2252. · DOI · Paper page
  4. 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://elsevier.com/books/the-theory-of-error-correcting-codes/macwilliams/978-0-444-85193-2.
  5. Daniel A. Lidar and Todd A. Brun. Quantum Error Correction. Cambridge University Press, 2013. 10.1017/CBO9781139034807. URL https://doi.org/10.1017/CBO9781139034807. · DOI · Paper page
  6. 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://doi.org/10.1016/s0003-4916(02)00018-0. · DOI · Paper page
  7. 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://doi.org/10.1007. · DOI · Paper page
  8. 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://doi.org/10.26421/QIC10.5. · doi:10.26421/qic10.5
  9. 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://dx.doi.org/10.1007/s12532-009-0002-8. · DOI · Paper page
  10. 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://doi.org/10.1016. · DOI · Paper page
  11. 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://doi.org/10.1103. · DOI · Paper page
  12. 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://doi.org/10.1103. · DOI · Paper page
  13. 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://doi.org/10.1109. · DOI
  14. 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://doi.org/10.1103. · DOI · Paper page
  15. 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://doi.org/10.1103. · DOI · Paper page
  16. 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://doi.org/10.1103. · DOI · Paper page
  17. 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://doi.org/10.1088. · DOI
  18. 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://doi.org/10.1103. · DOI · Paper page
  19. 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://doi.org/10.1109. · DOI · Paper page
  20. Sergey Bravyi. Lagrangian representation for fermionic linear optics. Quantum Information & Computation, 5 (3): 216-238, 2005. 10.26421/QIC5.3. URL https://doi.org/10.26421/QIC5.3. · doi:10.26421/qic5.3
  21. 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://dx.doi.org/10.1109/CIG.2010.5592866. · DOI · Paper page
  22. 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://doi.org/10.1088. · DOI · Paper page
  23. D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. ISBN 9780521642989. URL https://books.google.nl/books?id=AKuMj4PN_EMC.
  24. 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.google.nl/books?id=aefUBQAAQBAJ.
  25. 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://doi.org/10.26421/QIC8.10. · doi:10.26421/qic8.10
  26. 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://doi.org/10.1103. · DOI
  27. 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://doi.org/10.1103. · DOI · Paper page
  28. Nicolas Delfosse. Decoding color codes by projection onto surface codes. Physical Review A, 89 (1), jan 2014. 10.1103/physreva.89.012317. URL https://doi.org/10.1103. · DOI · Paper page
  29. 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://doi.org/10.1109. · DOI · Paper page
  30. John D. Hunter. Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9 (3): 90-95, 2007. 10.1109/mcse.2007.55. URL https://doi.org/10.1109. · DOI · Paper page
  31. 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://doi.org/10.1086. · DOI · Paper page

Cited by

See all 45

Metadata

Authors
Criger, B., & Ashraf, I.
Venue
Quantum
Published
2018-10-19
Volume
2
Pages
102
ISSN
2521-327X (ISSN-L)
OpenAlex
W2750849968
Cited by
45
References
14
FWCI
1.70
Type
journal article
Language
en
Open access
gold

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.