MWPM / Sparse Blossom (+ correlated matching) dec_mwpm

MWPM makes each detection event (a check whose outcome changed between rounds) a vertex on a weighted graph whose edges are the errors flipping two detectors; the lowest-weight pairing explaining the set is the most probable single error chain under independent errors — not the maximum-likelihood decoding, which sums over all chains in a class and is what the tensor-network and BP-based decoders approximate. Dennis, Kitaev, Landahl and Preskill introduced it (2002) D[650]; Fowler showed in 2015 that below threshold it can be solved exactly in average O(1) parallel time per round — on a 2D array of classical processors, each serving a fixed number of qubits, independent of lattice size D[725]. Correlated matching reweights edges so a Y error is not charged twice. The engine is Higgott and Gidney's Sparse Blossom (Quantum 9, 1600, 2025-01-20) D[726], a sparse reformulation of Edmonds' 1965 blossom algorithm, shipped as PyMatching v2.
a = 0.5 — classical post-processing, no carrier; b, c, d, e do not apply [graph].
f = Pauli chain on a matching graph; g = none — software, no fabrication [graph].

Throughput must exceed syndrome production or the backlog diverges and the machine stalls: Sparse Blossom clears ~10⁶ errors per core-second, under 1 µs per round at d=17 D[726], inside Willow's 1.1 µs cycle D[1]. Latency binds only where a logical measurement gates the next operation: 63 µs at d=5 is ~57 cycles of dead time D[1]. The accuracy floor is structural: matching finds the most probable single chain only when every error flips at most two detectors, and it never sums over the chains of one class as a maximum-likelihood decoder does, so hyperedges (Y errors, correlated measurement errors, leakage, loss) must be projected onto a matchable graph. That projection is the whole gap to a decoder modelling them — Λ = 2.04 ± 0.02 for matching against 2.14 ± 0.02 for the neural decoder on Willow's syndromes D[1], AlphaQubit ~25% better at simulated d=11 D[657]. What moves the floor is the graph: fitted edge weights, soft readout, leakage edges.

Dominant term: the decoding graph — mis-calibrated weights, unrepresented leakage — not the matcher D[1].

No fabrication: MIT-licensed software [728] on general compute, acceleration the paid, single-sourced layer. Every published real-time QEC decoder runs on AMD/Xilinx logic — Riverlane's on a VU19P at ≈6% of LUTs (lookup tables) for d≤17 D[238], Micro Blossom on a Versal VMK180 D[727], the Shenzhen neural decoder on a Kintex-7 D[729], IBM's Relay-BP on AMD parts P[48] — and GPU decoding is NVIDIA-only. No MWPM ASIC exists (4 Sep 2026). Export exposure is on that hardware: the BIS rule of 2024-09-06 controls quantum computers (4A906) and sub-4.5 K control ICs (3A901.a) G[301]; published decoder source is outside the EAR under 15 CFR §734.7.

At 10³ qubits one core suffices. At 10⁴ the binding term is syndrome bandwidth, not compute — d² detectors per logical qubit per 1.1 µs — hence cryogenic pre-compression, claimed at up to 3,780× below 0.56 mW at 4 K but not fabricated Sfact. At 10⁶ the interconnect decides: NVQLink's 3.84 µs round trip C[324] exceeds a transmon cycle, so GPU matching runs windowed there.

Default real-time decoder for surface- and colour-code memories, shared across five families [graph]: all three superconducting architectures, all three trapped-ion architectures, both Rydberg tweezer arrays, the fusion-based and continuous-variable photonic architectures, and both spin architectures — primary on six of the twelve (cat and GKP, dual-rail, the linear Paul trap, fusion photonics, quantum-dot and donor spins), alternate on the rest; it needs the near-planar graph a static nearest-neighbour lattice supplies free. It replaces neural and belief-propagation decoders, which win once checks stop being matchable; switching is asymmetric — leaving costs a hardware implementation and a new verification story, returning costs nothing. Clock contribution ≈1.0 µs per round at d=17 D[726] against a derived clock of 0.65 µs for the transmon surface-code architecture (derived clock = sum of the syndrome round: gate layers + transport + readout + reset for the architecture). Empty slot nearby: no real-time matcher consumes soft readout or leakage flags.

Sparse Blossom's throughput comes from simulated Stim streams D[726]. The one hardware-integrated figure, Willow's 63 µs at d=5, used a specialised parallel Sparse Blossom built by Google, not stock PyMatching D[1]. Micro Blossom's 0.8 µs at d=13 is peer-reviewed (ASPLOS 2025) but replays syndromes D[727]; the repository's 367 ns appears in no paper Cfact. The much-quoted threshold spread is no conflict: 0.7% (PyMatching), 0.65% and 0.55% (Riverlane's software and hardware clustering decoders) come from one comparison under one noise model D[238]. Every challenger publishes MWPM as baseline; none replicates its speed.

Quantum X Labs' claim that its transformer decoder outperforms MWPM carries no quantitative figure and no peer review [730]. Not published: a separate description, hardware platform or resource figure for the specialised Sparse Blossom variant that decodes Willow in real time, so its 63 µs cannot be attributed to a named part.

Who.
| Organisation | Role | Country | What they do | Evidence |
|---|---|---|---|---|
| Google Quantum AI | Developer/user | US | Co-authored Sparse Blossom; runs it in Willow | D[1], [726] |
| Riverlane | Supplier | UK | Sells Deltaflow QEC hardware; quotes MWPM as reference | Cfact |
| Yale University | Research | US | Micro Blossom exact-MWPM FPGA accelerator | D[727] |
| AMD | Supplier | US | Its parts carry every published real-time decoder | D[238], [727] |
| NVIDIA | Supplier | US | CUDA-Q QEC and the NVQLink GPU–QPU bus | C[324] |

Money. 2024-08-06 · Riverlane · Series C · $75 M (its roadmap says $85 M) · Planet First Partners lead · >$120 M cumulative · closed C[661]. 2025-11-17 · NVIDIA · NVQLink launch · undisclosed · Quantinuum first QPU partner Cfact. 2026-07-24 · Quantum X Labs · result · none disclosed · NVIDIA, Quantum Machines/IQCC · unquantified C[730]. No decoder-specific DARPA award exists; QBI funds eleven Stage B teams, each needing one fact. No later Riverlane round located as of 4 Sep 2026.

Market & supply chain. Nobody sells MWPM: the algorithm is free and the reference MIT-licensed [728], so value accrues to the box that runs it — Deltaflow, CUDA-Q QEC/NVQLink, in-house firmware. Concentration is one-deep twice: AMD for logic, NVIDIA for GPUs. The one public resource figure, ≈6% of a VU19P for d≤17 D[238], implies ~16 patches per part. Pays into G3 and G4.

IP & standards. No MWPM patent family — Edmonds (1965) via Dennis–Kitaev–Landahl–Preskill (2002) D[650]; PyMatching and Micro Blossom are MIT-licensed [727], [728]. The IP is on hardware decoders: Riverlane GB 2641501 A (published 2025-12-10), Google US 12,518,194 (granted 2026-01-06) fact. PatSnap counted 12 QEC patents in April 2026 (Google 6, IBM 4, Tencent 2), no decoder cluster P[668]. De facto interfaces: Stim detector-error models, NVQLink.

Roadmaps & track record. Higgott and Gidney (2023-03 · sub-µs decoding at scale · met, and inside Willow's loop) D[726]. Yale (2025-03 · d=13 at 0.8 µs on FPGA · met; the repository's 367 ns is not) D[727]. Riverlane (2026-03-12 · megaquop before 2030, teraquop from 2033 · no interim milestone due) R[658]. Google's claims track delivery and are the only ones measured live; Riverlane's roadmap is unfalsifiable before 2029.

Strategic reading. If matching holds, AMD and every surface-code builder win: the reference stays free and differentiation collapses to firmware. Riverlane's hardware decoder trades threshold (0.55% vs 0.7%) for latency and area D[238], so its moat is "under the cycle time" — which Micro Blossom now offers for exact MWPM, MIT-licensed D[727]. If matching loses it loses to belief propagation on qLDPC: decoder, code and connectivity change together.

Confirm/demote in 12–24 months: a same-qubit, same-calibration comparison of matching against a challenger (all current ones are simulated, offline or self-refereed); an FPGA matcher closing a live loop at d≥7. Best case 2029: matching stays default past 10⁴ physical qubits, reaction time down from 63 µs to ~1 µs. Worst case: qLDPC memories carry the machines and belief propagation owns the socket. Open questions: does matching extend to loss-dominated atom syndromes; will anyone fund a decoder ASIC when 6% of an FPGA suffices; will QBI Stage C fix a decoder-agnostic benchmark.