Sparse Blossom: correcting a million errors per core second with minimum-weight matching
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 alg...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-01-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-01-20-1600/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832593481541877760 |
|---|---|
| author | Oscar Higgott Craig Gidney |
| author_facet | Oscar Higgott Craig Gidney |
| author_sort | Oscar Higgott |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-83e448efb93041d7914ae85fc272352b |
| institution | Kabale University |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-83e448efb93041d7914ae85fc272352b2025-01-20T14:58:21ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-01-019160010.22331/q-2025-01-20-160010.22331/q-2025-01-20-1600Sparse Blossom: correcting a million errors per core second with minimum-weight matchingOscar HiggottCraig GidneyIn 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.https://quantum-journal.org/papers/q-2025-01-20-1600/pdf/ |
| spellingShingle | Oscar Higgott Craig Gidney Sparse Blossom: correcting a million errors per core second with minimum-weight matching Quantum |
| title | Sparse Blossom: correcting a million errors per core second with minimum-weight matching |
| title_full | Sparse Blossom: correcting a million errors per core second with minimum-weight matching |
| title_fullStr | Sparse Blossom: correcting a million errors per core second with minimum-weight matching |
| title_full_unstemmed | Sparse Blossom: correcting a million errors per core second with minimum-weight matching |
| title_short | Sparse Blossom: correcting a million errors per core second with minimum-weight matching |
| title_sort | sparse blossom correcting a million errors per core second with minimum weight matching |
| url | https://quantum-journal.org/papers/q-2025-01-20-1600/pdf/ |
| work_keys_str_mv | AT oscarhiggott sparseblossomcorrectingamillionerrorspercoresecondwithminimumweightmatching AT craiggidney sparseblossomcorrectingamillionerrorspercoresecondwithminimumweightmatching |