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; 12 of the 12 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

12 of 12 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

Show all 12 references

Research works printed but not linked: 33

  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. 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://dx.doi.org/10.1063/1.1499754. · DOI · Paper page
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. Guifré Vidal. Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters, 91 (14), oct 2003. 10.1103/physrevlett.91.147902. URL https://doi.org/10.1103. · DOI · Paper page
  23. 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
  24. 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
  25. 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.
  26. 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.
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
12
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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Multi-path Summation for Decoding 2D Topological Codes. https://app.cochat.ai/papers/10.22331/q-2018-10-19-102
The paper
Criger, B., & Ashraf, I. (2018). Multi-path Summation for Decoding 2D Topological Codes. Quantum. https://doi.org/10.22331/q-2018-10-19-102

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.