Sparse-Blossom Decoding in o(1) Time
Abstract
Matching-based decoding is widely used in quantum error correction, and accelerating it is key to enabling fast and scalable fault-tolerant quantum computation. Minimum-weight perfect matching (MWPM) decoding provides rigorous guarantees for error suppression, while sparse blossom enables its practical implementation at modest problem sizes. However, the runtime of existing sparse-blossom implementations unavoidably increases with problem size, motivating a rigorous parallelization framework that guarantees correctness and a runtime shorter than the syndrome-extraction timescale. Here, we present such a framework and prove that the resulting parallel sparse-blossom algorithm produces the same correction as the original, non-parallel sparse blossom. For the rotated surface code with code distance d and physical error rates below a finite threshold, we prove that the average parallel runtime of decoding for O(d) rounds of syndrome extraction is upper bounded by a quasi-polylogarithmic function of d. For a d-round decoding window, this implies that the average parallel runtime per round is o(1). We also perform numerical simulation to identify conditions under which the parallel runtime per round decreases with increasing code distance. These results suggest that increasing code distance need not lead to longer parallel decoding times, providing a foundation for scalable parallel matching-based decoding.
Related
- Patchwork: automated lattice surgery and space-time partitioning for real-time decoding
- Dithered Belief Propagation for Real-Time Quantum Memory Decoding
- Real-time BP decoding of a high-rate QEC code
- FTWeave: Composing Logical Execution, Real-Time Decoding, and Magic-State Supply in Tightly Integrated Quantum-Classical Systems
- Reconstruction of 4D Mitral Regurgitation Hemodynamics from Sparse Planar Data using Deep Operator Networks with Test-Time Adaptation
BibTeX
@misc{mikami2026sparseblossom,
title = {{Sparse-Blossom Decoding in $o(1)$ Time}},
author = {Ryo Mikami and Hayata Yamasaki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12262},
eprint = {2609.12262},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12262},
}
RIS
TY - UNPB
TI - Sparse-Blossom Decoding in o(1) Time
AU - Ryo Mikami
AU - Hayata Yamasaki
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.12262
UR - https://arxiv.org/abs/2609.12262
AB - Matching-based decoding is widely used in quantum error correction, and accelerating it is key to enabling fast and scalable fault-tolerant quantum computation. Minimum-weight perfect matching (MWPM) decoding provides rigorous guarantees for error suppression, while sparse blossom enables its practical implementation at modest problem sizes. However, the runtime of existing sparse-blossom implementations unavoidably increases with problem size, motivating a rigorous parallelization framework that guarantees correctness and a runtime shorter than the syndrome-extraction timescale. Here, we present such a framework and prove that the resulting parallel sparse-blossom algorithm produces the same correction as the original, non-parallel sparse blossom. For the rotated surface code with code distance d and physical error rates below a finite threshold, we prove that the average parallel runtime of decoding for O(d) rounds of syndrome extraction is upper bounded by a quasi-polylogarithmic function of d. For a d-round decoding window, this implies that the average parallel runtime per round is o(1). We also perform numerical simulation to identify conditions under which the parallel runtime per round decreases with increasing code distance. These results suggest that increasing code distance need not lead to longer parallel decoding times, providing a foundation for scalable parallel matching-based decoding.
ER -