CoChat
Sign Up
PreprintCited by 148Quantum Computing Algorithms and ArchitectureError Correcting Code TechniquesQuantum Information and Cryptography

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

Open access
Higgott, Oscar, Gidney, Craig·2023·arXiv
DOI 10.48550/arxiv.2303.15933arXiv 2303.15933
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.

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

DataCite · 10.48550/arxiv.2303.15933

Cites

Statistics

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

Self-check

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

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

Cites

No references could be resolved yet.

Research works printed but not linked: 52

  1. Ravindra K Ahuja, Kurt Mehlhorn, James Orlin, and Robert E Tarjan. "Faster algo- rithms for the shortest path problem". In: Journal of the ACM (JACM) 37.2 (1990), pp. 213-223. doi: 10.1145/77600.77615. · DOI
  2. Google Quantum AI. "Suppressing quantum errors by scaling a surface code logical qubit". In: Nature 614.7949 (Feb. 2023), pp. 676-681. issn: 1476-4687. doi: 10.1038/s41586- 022-05434-1. · DOI · Paper page
  3. Dave Bacon. "Operator quantum error-correcting subsystems for self-correcting quan- tum memories". In: Phys. Rev. A 73 (1 Jan. 2006), p. 012340. doi: 10.1103/Phys- RevA.73.012340. · DOI · Paper page
  4. F Barahona. "On the computational complexity of Ising spin glass models". In: Journal of Physics A: Mathematical and General 15.10 (Oct. 1982), p. 3241. doi: 10.1088/0305- 4470/15/10/028. · DOI
  5. Burak Boyacı, Thu Huong Dang, and Adam N. Letchford. "On matchings, T-joins, and arc routing in road networks". In: Networks 79.1 (2022), pp. 20-31. doi: 10.1002/net.22033. · DOI
  6. 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". In: Algorithms and Data Structures. Ed. by Frank Dehne, Jörg-Rüdiger Sack, Arvind Gupta, and Roberto Tamassia. Berlin, Heidelberg: Springer Berlin Hei- delberg, 1999, pp. 25-36. isbn: 978-3-540-48447-9. doi: 10.1007/3-540-48447-7˙3. · DOI
  7. Claude Berge. "Two theorems in graph theory". In: Proceedings of the National Academy of Sciences 43.9 (1957), pp. 842-844. doi: 10.1073/pnas.43.9.842. · DOI
  8. H. Bombin and M. A. Martin-Delgado. "Topological Quantum Distillation". In: Phys. Rev. Lett. 97 (18 Oct. 2006), p. 180501. doi: 10.1103/PhysRevLett.97.180501. · DOI · Paper page
  9. Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, and Martin Suchara. "Sub- system surface codes with three-qubit check operators". In: Quantum Info. Comput. 13.11-12 (Nov. 2013), pp. 963-985. issn: 1533-7146. doi: 10.26421/QIC13.11-12-4. · DOI
  10. Benjamin J. Brown. "Conservation Laws and Quantum Error Correction: Toward a Generalized Matching Decoder". In: IEEE BITS the Information Theory Magazine 2.3 (2022), pp. 5-19. doi: 10.1109/MBITS.2023.3246025. · DOI
  11. Sergey Bravyi, Martin Suchara, and Alexander Vargo. "Efficient algorithms for max- imum likelihood decoding in the surface code". In: Phys. Rev. A 90 (3 Sept. 2014), p. 032326. doi: 10.1103/PhysRevA.90.032326. · DOI · Paper page
  12. Nikolas P. Breuckmann and Barbara M. Terhal. "Constructions and Noise Threshold of Hyperbolic Surface Codes". In: IEEE Transactions on Information Theory 62.6 (2016), pp. 3731-3744. doi: 10.1109/TIT.2016.2555700. · DOI
  13. Rui Chao, Michael E. Beverland, Nicolas Delfosse, and Jeongwan Haah. "Optimization of the surface code design for Majorana-based qubits". In: Quantum 4 (Oct. 2020), p. 352. issn: 2521-327X. doi: 10.22331/q-2020-10-28-352. · DOI
  14. Poulami Das, Christopher A. Pattison, Srilatha Manne, Douglas M. Carmean, Krysta M. Svore, Moinuddin Qureshi, and Nicolas Delfosse. "AFS: Accurate, Fast, and Scal- able Error-Decoding for Fault-Tolerant Quantum Computers". In: 2022 IEEE In- ternational Symposium on High-Performance Computer Architecture (HPCA). 2022, pp. 259-273. doi: 10.1109/HPCA53966.2022.00027. · DOI
  15. Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. "Topological quan- tum memory". In: Journal of Mathematical Physics 43.9 (2002), pp. 4452-4505. doi: 10.1063/1.1499754. · DOI · Paper page
  16. Peter-Jan H. S. Derks, Alex Townsend-Teague, Ansgar G. Burchards, and Jens Eisert. "Designing fault-tolerant circuits using detector error models". In: (2024). arXiv: 240 7.13826 [quant-ph]. url: https://arxiv.org/abs/2407.13826. · arXiv
  17. Nicolas Delfosse and Naomi H. Nickerson. "Almost-linear time decoding algorithm for topological codes". In: Quantum 5 (Dec. 2021), p. 595. issn: 2521-327X. doi: 10.22331/q-2021-12-02-595. · DOI · Paper page
  18. Nicolas Delfosse and Gilles Zémor. "Linear-time maximum likelihood decoding of sur- face codes over the quantum erasure channel". In: Phys. Rev. Res. 2 (3 July 2020), p. 033042. doi: 10.1103/PhysRevResearch.2.033042. · DOI
  19. Jack Edmonds. "Maximum matching and a polyhedron with 0,1-vertices". In: Journal of Research of the National Bureau of Standards Section B Mathematics and Math- ematical Physics (1965), p. 125. doi: 10.6028/jres.069b.013. url: https : / / api . semanticscholar.org/CorpusID:15379135. · DOI
  20. Jack Edmonds. "Paths, Trees, and Flowers". In: Canadian Journal of Mathematics 17 (1965), pp. 449-467. doi: 10.4153/CJM-1965-045-4. · DOI · Paper page
  21. Jack Edmonds and Ellis L. Johnson. "Matching, Euler tours and the Chinese post- man". In: Mathematical Programming 5.1 (Dec. 1973), pp. 88-124. issn: 1436-4646. doi: 10.1007/BF01580113. · DOI
  22. Austin G Fowler. "Optimal complexity correction of correlated errors in the surface code". In: arXiv preprint arXiv:1310.0863 (2013). · arXiv
  23. Austin G. Fowler. "Minimum weight perfect matching of fault-tolerant topological quantum error correction in average O(1) parallel time". In: Quantum Info. Comput. 15.1-2 (Jan. 2015), pp. 145-158. issn: 1533-7146. doi: 10.26421/QIC15.1-2-9. · DOI
  24. Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg. "Towards Practical Classical Processing for the Surface Code". In: Phys. Rev. Lett. 108 (18 May 2012), p. 180501. doi: 10.1103/PhysRevLett.108.180501. · DOI
  25. Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg. "Towards practical classical processing for the surface code: Timing analysis". In: Phys. Rev. A 86 (4 Oct. 2012), p. 042313. doi: 10.1103/PhysRevA.86.042313. url: https://link.aps.org/ doi/10.1103/PhysRevA.86.042313. · DOI
  26. Ed. by Giorgio Ausiello and Marco Protasi. Berlin, Heidelberg: Springer Berlin Hei- delberg, 1983, pp. 90-113. isbn: 978-3-540-38714-5. doi: 10.1007/3-540-12727-5˙4. · DOI
  27. Craig Gidney, Michael Newman, Austin Fowler, and Michael Broughton. "A Fault- Tolerant Honeycomb Memory". In: Quantum 5 (Dec. 2021), p. 605. issn: 2521-327X. doi: 10.22331/q-2021-12-20-605. · DOI · Paper page
  28. Craig Gidney. "Stim: a fast stabilizer circuit simulator". In: Quantum 5 (July 2021), p. 497. issn: 2521-327X. doi: 10.22331/q-2021-07-06-497. · DOI · Paper page
  29. Craig Gidney and Cody Jones. "New circuits and an open source decoder for the color code". In: (2023). arXiv: 2312.08813 [quant-ph]. url: https://arxiv.org/abs/ 2312.08813. · arXiv
  30. Oscar Higgott and Nikolas P. Breuckmann. "Subsystem Codes with High Thresholds by Gauge Fixing and Reduced Qubit Overhead". In: Phys. Rev. X 11 (3 Aug. 2021), p. 031039. doi: 10.1103/PhysRevX.11.031039. · DOI · Paper page
  31. Matthew B. Hastings and Jeongwan Haah. "Dynamically Generated Logical Qubits". In: Quantum 5 (Oct. 2021), p. 564. issn: 2521-327X. doi: 10.22331/q-2021-10-19-564. · DOI · Paper page
  32. Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell. "Improved Decoding of Circuit Noise and Fragile Boundaries of Tai- lored Surface Codes". In: Phys. Rev. X 13 (3 July 2023), p. 031007. doi: 10.1103/Phys- RevX.13.031007. · DOI
  33. Oscar Higgott. "PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching". In: ACM Transactions on Quantum Computing 3.3 (June 2022). doi: 10.1145/3505637. · DOI · Paper page
  34. Shilin Huang, Michael Newman, and Kenneth R. Brown. "Fault-tolerant weighted union-find decoding on the toric code". In: Phys. Rev. A 102 (1 July 2020), p. 012419. doi: 10.1103/PhysRevA.102.012419. · DOI
  35. Aleksander Kubica and Nicolas Delfosse. "Efficient color code decoders in d ≥ 2 dimensions from toric code decoders". In: Quantum 7 (Feb. 2023), p. 929. issn: 2521- 327X. doi: 10.22331/q-2023-02-21-929. · DOI
  36. Vladimir Kolmogorov. "Blossom V: a new implementation of a minimum cost perfect matching algorithm". In: Mathematical Programming Computation 1.1 (July 2009), pp. 43-67. issn: 1867-2957. doi: 10.1007/s12532-009-0002-8. · DOI
  37. Bernhard H Korte and Jens Vygen. Combinatorial optimization. Springer, 2018. isbn: 978-3-662-56039-6. doi: 10.1007/978-3-662-56039-6. · DOI
  38. Namitha Liyanage, Yue Wu, Alexander Deters, and Lin Zhong. "Scalable Quantum Error Correction for Surface Codes using FPGA". In: 2023 IEEE 31st Annual Inter- national Symposium on Field-Programmable Custom Computing Machines (FCCM). 2023, pp. 217-217. doi: 10.1109/FCCM57271.2023.00045. · DOI
  39. Matt McEwen, Dave Bacon, and Craig Gidney. "Relaxing Hardware Requirements for Surface Code Circuits using Time-dynamics". In: Quantum 7 (Nov. 2023), p. 1172. issn: 2521-327X. doi: 10.22331/q-2023-11-07-1172. · DOI
  40. Mikhail V Menshikov. "Coincidence of critical points in percolation problems". In: Soviet Mathematics Doklady. Vol. 33. 1986, pp. 856-859.
  41. Jiri Matoušek and Bernd Gärtner. Understanding and using linear programming. Springer, 2007. isbn: 978-3-540-30697-9. doi: 10.1007/978-3-540-30717-4. · DOI
  42. Kai Meinerz, Chae-Yeun Park, and Simon Trebst. "Scalable Neural Decoder for Topo- logical Surface Codes". In: Phys. Rev. Lett. 128 (8 Feb. 2022), p. 080505. doi: 10.1103/Phys- RevLett.128.080505. · DOI
  43. Martin Suchara, Sergey Bravyi, and Barbara Terhal. "Constructions and noise thresh- old of topological subsystem codes". In: Journal of Physics A: Mathematical and The- oretical 44.15 (Mar. 2011), p. 155301. doi: 10.1088/1751-8113/44/15/155301. · DOI
  44. Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, and Earl T. Camp- bell. "Parallel window decoding enables scalable fault tolerant quantum computa- tion". In: Nature Communications 14.1 (Nov. 2023), p. 7040. issn: 2041-1723. doi: 10.1038/s41467-023-42482-1. · DOI
  45. Neereja Sundaresan, Theodore J. Yoder, Youngseok Kim, Muyuan Li, Edward H. Chen, Grace Harper, Ted Thorbeck, Andrew W. Cross, Antonio D. Córcoles, and Maika Takita. "Demonstrating multi-round subsystem quantum error correction using matching and maximum likelihood decoders". In: Nature Communications 14.1 (May 2023), p. 2852. issn: 2041-1723. doi: 10.1038/s41467-023-38247-5. · DOI · Paper page
  46. Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi, and Jianxin Chen. "Scalable Surface- Code Decoders with Parallelization in Time". In: PRX Quantum 4 (4 Dec. 2023), p. 040344. doi: 10.1103/PRXQuantum.4.040344. · DOI
  47. Barbara M. Terhal. "Quantum error correction for quantum memories". In: Rev. Mod. Phys. 87 (2 Apr. 2015), pp. 307-346. doi: 10.1103/RevModPhys.87.307. · DOI · Paper page
  48. Giacomo Torlai and Roger G. Melko. "Neural Decoder for Topological Codes". In: Phys. Rev. Lett. 119 (3 July 2017), p. 030501. doi: 10.1103/PhysRevLett.119.030501. · DOI
  49. David Kingsley Tuckett. "Tailoring surface codes: Improvements in quantum error correction with biased noise". (qecsim: https://github.com/qecsim/qecsim). PhD thesis. University of Sydney, 2020. doi: 10.25910/x8xw-9077. · DOI
  50. W. T. Tutte. "The Factorization of Linear Graphs". In: Journal of the London Math- ematical Society s1-22.2 (1947), pp. 107-111. doi: 10.1112/jlms/s1-22.2.107. · DOI
  51. Yue Wu, Namitha Liyanage, and Lin Zhong. "An interpretation of Union-Find De- coder on Weighted Graphs". In: (2022). arXiv: 2211.03288 [quant-ph]. · arXiv
  52. Yue Wu and Lin Zhong. "Fusion Blossom: Fast MWPM Decoders for QEC". In: 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 01. 2023, pp. 928-938. doi: 10.1109/QCE57702.2023.00107. A Compressed tracking in Union-Find Compressed tracking can be naturally adapted to the Union-Find decoder [DN21; HNB20], as shown in Figure 15. Each detection event is initialised with a region, which we refer to as a cluster, to be consistent with Ref. · DOI · Paper page

Cited by

Sorted by citations

Authors
Higgott, O., & Gidney, C.
Affiliations
Google (United States) (US)
ORCID
Higgott, Oscar
Venue
arXiv
Publisher
arXiv
Published
2023
Volume
9
Pages
1600-1600
ISSN
2521-327X (ISSN-L)
DOI
10.48550/arxiv.2303.15933
arXiv
2303.15933
OpenAlex
W4406617380
Cited by
148
References
0
Citations by year
2026: 53 · 2025: 72 · 2024: 18 · 2023: 5
FWCI
50.14
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 › Computer Science › Artificial Intelligence › 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