Multi-path Summation for Decoding 2D Topological Codes
Open accessThe 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.
Integrity signals
Registry
Cites
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.
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
Exploring Network Structure, Dynamics, and Function Using NetworkX
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008) · Proceedings of the Python in Science Conference · doi:10.25080/tcwv9851 · Cited by 7,477
seaborn: statistical data visualization
Waskom, M. (2021) · Journal of Open Source Software · doi:10.21105/joss.03021 · Cited by 7,310
Georgescu, I. M., Ashhab, S., & Nori, F. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.153 · Cited by 2,932
Edmonds, J. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-045-4 · Cited by 2,428 · cited 1×
“Finding minimal-weight perfect matchings is a well-known combinatorial problem, solved using the Blossom algorithm [14, 15].”
MethodTheory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593
Quantum codes on a lattice with boundary
Bravyi, S. B., & Kitaev, A. Y. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9811052 · Cited by 394
Quantum Circuits That Can Be Simulated Classically in Polynomial Time
Valiant, L. G. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700377025 · Cited by 311
Ultrahigh Error Threshold for Surface Codes with Biased Noise
Tuckett, D. K., Bartlett, S. D., & Flammia, S. T. (2018) · Physical Review Letters · doi:10.1103/physrevlett.120.050505 · Cited by 216 · cited 1×
“This has also been observed in predictions of logical error rates [37] and when using highly-correlated error models [38].”
ResultEfficient algorithms for maximum likelihood decoding in the surface code
Bravyi, S., Suchara, M., & Vargo, A. (2014) · Physical Review A · doi:10.1103/physreva.90.032326 · Cited by 214 · cited 1×
“In a recent departure from MWPM-based decoding, Bravyi, et al. [25] have introduced polynomial-time maximum-likelihood decoders for surface codes which are based on efficient sub-theories of quantum mechanics.”
MethodOptimal resources for topological two-dimensional stabilizer codes: Comparative study
Bombin, H., & Martin-Delgado, M. A. (2007) · Physical Review A · doi:10.1103/physreva.76.012305 · Cited by 178
Research works printed but not linked: 33
- 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
- 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
- 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
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
Suppressing quantum errors by scaling a surface code logical qubit
Google Quantum, A. I., Acharya, R., Aleiner, I., Allen, R., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Atalaya, J., et al. (2023) · Nature · doi:10.1038/s41586-022-05434-1 · Cited by 1,103
“Like the correlated MWPM decoder, the belief-matching decoder exploits information about hyperedge fault mechanisms, but in a different way - by combining belief propagation (BP) with MWPM [51, 52].”
Quantum error correction: an introductory guide
Roffe, J. (2019) · Contemporary Physics · doi:10.1080/00107514.2019.1667078 · Cited by 356
Decoding across the quantum low-density parity-check code landscape
Roffe, J., White, D. R., Burton, S., & Campbell, E. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043423 · Cited by 192
Decoding algorithms for surface codes
deMarti iOlius, A., Fuentes, P., Orús, R., Crespo, P. M., & Etxezarreta Martinez, J. (2024) · Quantum · doi:10.22331/q-2024-10-10-1498 · Cited by 60
“The decoding complexity of the algorithm was maintained when compared to MWPM when parallel processing was allowed (Criger and Ashraf, 2018).”
MethodResultGeneral tensor network decoding of 2D Pauli codes
Chubb, C. T. (2021) · arXiv · doi:10.48550/arxiv.2101.04125 · Cited by 20
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.