Sparse Blossom: correcting a million errors per core second with minimum-weight matching
By Oscar Higgott, Craig Gidney. Quantum, 2023
355 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence
View Paper: https://www.semanticscholar.org/paper/eb57a5cc2ea992a9f1469752d56c61de84798c6f
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Göran Wendin
- Jarrod R. McClean
- Craig Gidney
- Jay M. Gambetta
- Hartmut Neven
- Oscar Higgott
- Sergey Bravyi
- Cody Jones
Citations in the corpus
- Quantum error correction below the surface code threshold (2024, positive): “We employ a specialized version of the Sparse Blossom algorithm [42] optimized to quickly resolve local configurations of errors common in surface code decoding, using a parallelization strategy similar to Ref.”
- High-threshold and low-overhead fault-tolerant quantum memory (2023, methodology): “This stage is analogous to computing the decoding graph in error correction algorithms based on the surface code [50, 51].”
- Magic state cultivation: growing T states as cheap as CNOT gates (2024, methodology): ““pymatching-gap” means pymatching was used to compute a complementary gap [HG23; Gid+23].”