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

Article · Oscar Higgott, Craig Gidney

- Archive id: arxiv:2303.15933
- Published: 2025-01-20
- Venue: Quantum
- DOI: https://doi.org/10.22331/q-2025-01-20-1600
- arXiv: https://arxiv.org/abs/2303.15933
- Citations: 148
- Source URL: https://doi.org/10.22331/q-2025-01-20-1600
- PDF: https://quantum-journal.org/papers/q-2025-01-20-1600/pdf/
- Provenance: openalex+arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Error Correction & Fault Tolerance](https://space-kitty.com/topics/quantum-error-correction)

Cited in dossiers:
- [Quantum Error Correction & Fault Tolerance: State of the Field (October 2026)](https://space-kitty.com/dossiers/quantum-error-correction)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.