Surface code decoders like Minimum Weight Perfect Matching (MWPM) can also be used to estimate or bound the probability of a logical failure conditioned on the error syndrome commonly called ``soft outputs''. Estimates like the complementary gap of a matching, or others like the ``cluster gap'' are used to produce high fidelity magic states via post-selection. They are also helpful in reducing the overhead of fault-tolerant computation via code concatenation schemes like yoked surface codes. In this work we provide techniques to tightly lower bound the complementary gap of a rotated surface code syndrome block and provide fast parallel algorithms for computing this lower bound efficiently. Our algorithms run in real time for the moderate distances and reasonable physical noise rates required by these applications. We achieve latencies of the order of one to tens of microseconds on sufficiently fast CPU cores.
Surface code decoders like Minimum Weight Perfect Matching (MWPM) can also be used to estimate or bound the probability of a logical failure conditioned on the error syndrome commonly called soft outputs''. Estimates like the complementary gap of a matching, or others like the cluster gap'' are used to produce high fidelity magic states via post-selection. They are also helpful in reducing the overhead of fault-tolerant computation via code concatenation schemes like yoked surface codes. In this work we provide techniques to tightly lower bound the complementary gap of a rotated surface code syndrome block and provide fast parallel algorithms for computing this lower bound efficiently. Our algorithms run in real time for the moderate distances and reasonable physical noise rates required by these applications. We achieve latencies of the order of one to tens of microseconds on sufficiently fast CPU cores.
Decoders that provide an estimate of the probability of a logical failure conditioned on the error syndrome ("soft-output decoders") can reduce the overhead cost of fault-tolerant quantum memory and computation. In this work, we construct efficient soft-output decoders for the surface code derived from the Minimum-Weight Perfect Matching and Union-Find decoders. We show that soft-output decoding can improve the performance of a "hierarchical code," a concatenated scheme in which the inner code is the surface code, and the outer code is a high-rate quantum low-density parity-check code. Alternatively, the soft-output decoding can improve the reliability of fault-tolerant circuit sampling by flagging those runs that should be discarded because the probability of a logical error is intolerably large.
Sparse-Blossom Decoding in o(1) Time
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.
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.
Minimum-Weight Perfect Matching (MWPM) decoding is important to quantum error correction decoding because of its accuracy. However, many believe that it is difficult, if possible at all, to achieve the microsecond latency requirement posed by superconducting qubits. This work presents the first publicly known MWPM decoder, called Micro Blossom, that achieves sub-microsecond decoding latency. Micro Blossom employs a heterogeneous architecture that carefully partitions a state-of-the-art MWPM decoder between software and a programmable accelerator with parallel processing units, one of each vertex/edge of the decoding graph. On a surface code with code distance d and a circuit-level noise model with physical error rate p, Micro Blossom's accelerator employs O(d3) parallel processing units to reduce the worst-case latency from O(d12) to O(d9) and reduce the average latency from O(pd3+1) to O(p2 d2+1) when p «1.
To utilize quantum error-correcting codes, a decoder must infer the logical sector from the measured syndrome. Beyond a hard logical decision, some decoders provide soft information estimating its reliability. For minimum-weight perfect matching (MWPM), a common confidence measure is the complementary, or logical, gap. Neural-network decoders trained with binary cross entropy naturally output a different score, the logit, whose relation to the matching gap remains unclear. Here, we test whether the logit of a graph neural network (GNN) decoder behaves as a learned proxy for the logical gap. Using a pretrained GNN for the rotated surface code under uniform circuit-level noise [PRR, 7(2):023181, 2025], we compare its logit with the MWPM gap shot by shot on identical syndromes. The native GNN decoder-logit pair yields a lower post-selected logical error rate than the native MWPM decoder-gap pair over the operationally relevant range of acceptance rates. Exchanging the scores between decoders isolates score discrimination from hard-decision accuracy and shows that both contribute to the advantage. At larger distances each score best ranks failures of its own decoder, whereas at small distance, where the bounded matching gap saturates, the learned confidence better discriminates MWPM failures than the gap itself. Finally, GNN confidence is substantially better described by the posterior logistic form implied by an ideal log-likelihood ratio, while the MWPM gap shows systematic departures. Thus, a neural-network decoder trained only on syndromes and logical labels learns a gap-like confidence proxy whose native scale more closely follows the expected posterior calibration form, supporting learned soft output when MWPM gap estimates are unavailable, costly, or insufficiently expressive.
Efficient and realistic error decoding is crucial for fault-tolerant quantum computation (FTQC) on near-term devices. While decoding is a classical post-processing task, its effectiveness depends on accurately modeling quantum noise, which is hardware-dependent. In particular, correlated bit-flip (X) and phase-flip (Z) errors often arise under circuit-level noise. We introduce the Iterative Reweighting Minimum-Weight Perfect Matching (IRMWPM) decoder, which systematically incorporates such correlations to enhance quantum error correction. Our method leverages fault-detection patterns to guide reweighting: correlated X and Z detection events are identified, and their conditional probabilities update weights on the primal and dual lattices. This iterative procedure improves handling of realistic error propagation in a hardware-agnostic yet noise-aware manner. We prove that IRMWPM converges in finite time while preserving the distance guarantee of MWPM. Numerical results under circuit-level noise show substantial improvements. For distances ≥17 and physical error rates ≤0.001, IRMWPM reduces logical error rates by over 20x with only a few iterations. It also raises the accuracy threshold from 1% to 1.16%, making it practical for near-term real-time decoding. Extrapolated estimates suggest that to reach logical error rate 10−16, IRMWPM requires distance d=31, while standard MWPM needs d=50, implying a major reduction in qubit overhead.