CoChat
Sign Up
Cited by 180Quantum Computing Algorithms and ArchitectureError Correcting Code TechniquesQuantum Information and Cryptography

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

Sparse Blossom: correcting a million errors per core second with minimum-weight matching

Open access
Higgott, Oscar, Gidney, Craig·2025·Quantum
DOI 10.22331/q-2025-01-20-1600
Open this paper in CoChat — free accountOpen PDF

Abstract

In this work, we introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder, the most widely used decoder for several important families of quantum error correcting codes, including surface codes. Our algorithm, which we call sparse blossom, is a variant of the blossom algorithm which directly solves the decoding problem relevant to quantum error correction. Sparse blossom avoids the need for all-to-all Dijkstra searches, common amongst MWPM decoder implementations. For 0.1% circuit-level depolarising noise, sparse blossom processes syndrome data in both X and Z bases of distance-17 surface code circuits in less than one microsecond per round of syndrome extraction on a single core, which matches the rate at which syndrome data is generated by superconducting quantum computers. Our implementation is open-source, and has been released in version 2 of the PyMatching library.

Overview

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

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Integrity signals

Registry

Crossref · 10.22331/q-2025-01-20-1600

Cites

6 of 6 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.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • MWPM in its standard formulation requires that the decoding problem has a graph structure, that is, each error can flip at most two syndromes.

    “However, MWPM in its standard formulation requires that the decoding problem has a graph structure, that is, each error can flip at most two syndromes [184].”

    From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [184]

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

Flagged first, then by citations

Research works printed but not linked: 42

  1. Ravindra K Ahuja, Kurt Mehlhorn, James Orlin, and Robert E Tarjan, ``Faster algorithms for the shortest path problem'' Journal of the ACM (JACM) 37, 213-223 (1990). · DOI
  2. Dave Bacon ``Operator quantum error-correcting subsystems for self-correcting quantum memories'' Phys. Rev. A 73, 012340 (2006). · DOI · Paper page
  3. F Barahona ``On the computational complexity of Ising spin glass models'' Journal of Physics A: Mathematical and General 15, 3241 (1982). · DOI
  4. Burak Boyacı, Thu Huong Dang, and Adam N. Letchford, ``On matchings, T-joins, and arc routing in road networks'' Networks 79, 20–31 (2022). · DOI
  5. Piotr Berman, Andrew B. Kahng, Devendra Vidhani, and Alexander Zelikovsky, ``The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout'' Algorithms and Data Structures 25–36 (1999). · DOI
  6. Claude Berge ``Two theorems in graph theory'' Proceedings of the National Academy of Sciences 43, 842–844 (1957). · DOI
  7. H. Bombinand M. A. Martin-Delgado ``Topological Quantum Distillation'' Phys. Rev. Lett. 97, 180501 (2006). · DOI · Paper page
  8. Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, and Martin Suchara, ``Subsystem surface codes with three-qubit check operators'' Quantum Info. Comput. 13, 963–985 (2013). · DOI
  9. Benjamin J. Brown ``Conservation Laws and Quantum Error Correction: Toward a Generalized Matching Decoder'' IEEE BITS the Information Theory Magazine 2, 5–19 (2022). · DOI
  10. Sergey Bravyi, Martin Suchara, and Alexander Vargo, ``Efficient algorithms for maximum likelihood decoding in the surface code'' Phys. Rev. A 90, 032326 (2014). · DOI · Paper page
  11. Nikolas P. Breuckmannand Barbara M. Terhal ``Constructions and Noise Threshold of Hyperbolic Surface Codes'' IEEE Transactions on Information Theory 62, 3731–3744 (2016). · DOI
  12. Rui Chao, Michael E. Beverland, Nicolas Delfosse, and Jeongwan Haah, ``Optimization of the surface code design for Majorana-based qubits'' Quantum 4, 352 (2020). · DOI
  13. Poulami Das, Christopher A. Pattison, Srilatha Manne, Douglas M. Carmean, Krysta M. Svore, Moinuddin Qureshi, and Nicolas Delfosse, ``AFS: Accurate, Fast, and Scalable Error-Decoding for Fault-Tolerant Quantum Computers'' 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA) 259–273 (2022). · DOI
  14. Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill, ``Topological quantum memory'' Journal of Mathematical Physics 43, 4452–4505 (2002). · DOI · Paper page
  15. Nicolas Delfosseand Naomi H. Nickerson ``Almost-linear time decoding algorithm for topological codes'' Quantum 5, 595 (2021). · DOI · Paper page
  16. Nicolas Delfosseand Gilles Zémor ``Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel'' Phys. Rev. Res. 2, 033042 (2020). · DOI
  17. Jack Edmonds ``Maximum matching and a polyhedron with 0,1-vertices'' Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics 125 (1965). · DOI
  18. Jack Edmondsand Ellis L. Johnson ``Matching, Euler tours and the Chinese postman'' Mathematical Programming 5, 88–124 (1973). · DOI
  19. Austin G Fowler ``Optimal complexity correction of correlated errors in the surface code'' arXiv preprint arXiv:1310.0863 (2013). · arXiv
  20. Austin G. Fowler ``Minimum weight perfect matching of fault-tolerant topological quantum error correction in average O(1) parallel time'' Quantum Info. Comput. 15, 145–158 (2015). · DOI
  21. Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg, ``Towards Practical Classical Processing for the Surface Code'' Phys. Rev. Lett. 108, 180501 (2012). · DOI
  22. Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg, ``Towards practical classical processing for the surface code: Timing analysis'' Phys. Rev. A 86, 042313 (2012). · DOI
  23. Zvi Galil ``Efficient algorithms for finding maximal matching in graphs'' CAAP'83 90–113 (1983). · DOI
  24. Oscar Higgottand Nikolas P. Breuckmann ``Subsystem Codes with High Thresholds by Gauge Fixing and Reduced Qubit Overhead'' Phys. Rev. X 11, 031039 (2021). · DOI · Paper page
  25. Matthew B. Hastingsand Jeongwan Haah ``Dynamically Generated Logical Qubits'' Quantum 5, 564 (2021). · DOI · Paper page
  26. 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'' Phys. Rev. X 13, 031007 (2023). · DOI
  27. Oscar Higgott ``PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching'' ACM Transactions on Quantum Computing 3 (2022). · DOI · Paper page
  28. Shilin Huang, Michael Newman, and Kenneth R. Brown, ``Fault-tolerant weighted union-find decoding on the toric code'' Phys. Rev. A 102, 012419 (2020). · DOI
  29. Aleksander Kubicaand Nicolas Delfosse ``Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders'' Quantum 7, 929 (2023). · DOI
  30. Vladimir Kolmogorov ``Blossom V: a new implementation of a minimum cost perfect matching algorithm'' Mathematical Programming Computation 1, 43–67 (2009). · DOI
  31. Bernhard H Korteand Jens Vygen ``Combinatorial optimization'' Springer (2018). · DOI
  32. Namitha Liyanage, Yue Wu, Alexander Deters, and Lin Zhong, ``Scalable Quantum Error Correction for Surface Codes using FPGA'' 2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) 217–217 (2023). · DOI
  33. Matt McEwen, Dave Bacon, and Craig Gidney, ``Relaxing Hardware Requirements for Surface Code Circuits using Time-dynamics'' Quantum 7, 1172 (2023). · DOI
  34. Jiri Matoušekand Bernd Gärtner ``Understanding and using linear programming'' Springer (2007). · DOI
  35. Kai Meinerz, Chae-Yeun Park, and Simon Trebst, ``Scalable Neural Decoder for Topological Surface Codes'' Phys. Rev. Lett. 128, 080505 (2022). · DOI
  36. Martin Suchara, Sergey Bravyi, and Barbara Terhal, ``Constructions and noise threshold of topological subsystem codes'' Journal of Physics A: Mathematical and Theoretical 44, 155301 (2011). · DOI
  37. Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, and Earl T. Campbell, ``Parallel window decoding enables scalable fault tolerant quantum computation'' Nature Communications 14, 7040 (2023). · DOI
  38. Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi, and Jianxin Chen, ``Scalable Surface-Code Decoders with Parallelization in Time'' PRX Quantum 4, 040344 (2023). · DOI
  39. Giacomo Torlaiand Roger G. Melko ``Neural Decoder for Topological Codes'' Phys. Rev. Lett. 119, 030501 (2017). · DOI
  40. David Kingsley Tuckett ``Tailoring surface codes: Improvements in quantum error correction with biased noise'' thesis (2020) (qecsim: https://github.com/qecsim/qecsim). · DOI
  41. W. T. Tutte ``The Factorization of Linear Graphs'' Journal of the London Mathematical Society s1-22, 107–111 (1947). · DOI
  42. Yue Wuand Lin Zhong ``Fusion Blossom: Fast MWPM Decoders for QEC'' 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 01, 928–938 (2023). · DOI · Paper page

Cited by

Sorted by citations

Metadata

Authors
Higgott, O., & Gidney, C.
Affiliations
Google (United States) (US)
ORCID
Higgott, Oscar
Venue
Quantum
Publisher
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
Published
2025-01-20
Volume
9
Pages
1600
ISSN
2521-327X (ISSN-L)
DOI
10.22331/q-2025-01-20-1600
OpenAlex
W4406617380
Cited by
180
References
6
Citations by year
2026: 57 · 2025: 83
FWCI
45.64
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
minimum-weight perfect matching, blossom algorithm, quantum error correction, surface code, syndrome decoding, superconducting quantum computing

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