Micro Blossom: Accelerated Minimum-Weight Perfect Matching Decoding for Quantum Error Correction

A quantum computer measures its error-detection circuits roughly a million times a second and needs the answer back within about a microsecond, and the most accurate way to work out what went wrong — a classical graph matching algorithm from 1965 — was widely believed too intricate to build in hardware, so the field settled for approximations that produce up to fourteen times more logical errors; Micro Blossom (Yale) shows the belief was about the wrong granularity, splitting the algorithm so its irregular bookkeeping stays in software while its numerical half runs on one tiny processor per graph vertex and edge, reaching 0.8 microseconds at a code distance of 13.

Why this problem is worth solving

The thing that makes this a systems problem rather than a physics one is a deadline.

That coupling produces a counterintuitive consequence the paper spells out.

What people did before, and where it broke

• Run the exact algorithm on the dense graph of observed defects. The classical formulation builds a fully connected graph over the flipped measurements and matches on it. Where it broke. That graph has a number of edges quadratic in the defects, which is far more work than necessary.
• Run it on the sparse graph of possible errors instead. Two recent software decoders do this, adapting the algorithm to work directly on the decoding graph, which brings average time down to nearly linear. Where it broke. Nearly linear is still not a microsecond. The fastest reported exact software decoder remains roughly eight times short of the target at a code distance of 13.
• Parallelise across cores by splitting measurement rounds into blocks. One system processes blocks concurrently and fuses the results. Where it broke. That improves throughput, not latency — and latency is what the deadline is about. A decoder that keeps up on average but answers slowly still leaves the qubit waiting.
• Give up on exactness and approximate. Several hardware decoders do, and they genuinely reach the deadline. Where it broke. They pay in logical errors: 1.7 times more for one, 13.9 times more for another, at a code distance of 13. Others handle only simple cases, which implicitly assumes small codes and low error rates.
• Accept that the algorithm cannot be accelerated. This is the stated consensus, and it is a reasonable reading — the algorithm maintains nested structures and trees with merges and pointers, which is the opposite of what accelerators do well. Where it broke. It treats the algorithm as monolithic. Roughly two thirds of the time in a fast software implementation goes into a phase that turns out to be entirely local.
• The gap. Nobody had asked which parts of the algorithm are awkward. The answer is that the bookkeeping is and the numerics are not, and the numerics are where the time goes.

How Micro Blossom splits the algorithm

The idea

Waiting is itself a source of errors, so latency and accuracy are the same currency. The paper’s framing device is a small piece of arithmetic that reorganises how one should think about decoders. A qubit awaiting a verdict keeps being measured, and keeps accumulating errors, so the error rate it effectively suffers scales with how long the decoder takes relative to the code distance. Work the numbers for a distance-21 code with microsecond measurement cycles and the conclusion is uncomfortable: an approximate decoder with five times the logical error rate of the exact one comes out ahead, because it is fast enough that the arithmetic favours it. That is the honest case for approximation, and it is also the case this paper is trying to dissolve — if the exact decoder were fast enough, nobody would need to make that trade. The observation that approximating the matching buys speed at a measurable cost in logical errors is exactly what the approximate real-time decoding work covered elsewhere on this site was built around.

Fine-grained parallelism was available all along, hiding inside a phase everyone treated as monolithic. The published view is that this algorithm is too complex for hardware, and read as a statement about the whole algorithm it is defensible — it maintains nested structures, trees with merges, pointers between them. But the algorithm has two alternating halves, and profiling shows most of the time in the numerical one, which grows a budget uniformly across the graph. The paper’s central algorithmic contribution is rewriting that phase so the global information it needed is distributed down into per-vertex state, after which each vertex can act knowing only itself and its neighbours. That makes it a perfect fit for one processing unit per vertex and per edge with purely local wiring, and it drops the worst-case complexity by a factor of the graph size. Instantiating a processing element per graph element and communicating only with neighbours is the same design as the fine-grained graph mining accelerator work covered elsewhere on this site.

Offloading the common case is what removes the second bottleneck. With the numerics in hardware, the processor still had to exchange at least one read and one write per defect, and at hundreds of nanoseconds per exchange that became the limiting term. The escape is a probabilistic argument rather than an engineering one. Errors are independent and rare, so the overwhelmingly common situation is a single error sitting alone with nothing adjacent, and the paper proves that case can be settled entirely in hardware in constant time. What remains for software is the second-order event of two errors landing near each other, whose probability is the square of a small number. That turns the average interaction count from proportional to the error rate into proportional to its square. Keeping a fast path for the case that almost always happens and escalating only the rare one is the same structure as the better-than-worst-case decoding work covered elsewhere on this site.

Walking one round of measurements through the decoder

Streaming rather than batching is deliberate. Waiting for all rounds before starting would mean the entire decode happens after the last measurement, whereas folding each round in as it arrives means most of the work is already done when the last one lands.

Why it works

• Latency and accuracy are the same quantity, so an exact decoder that is fast dominates both alternatives. A qubit waiting on a verdict accumulates errors in proportion to the wait → so an approximate decoder can win on the sum despite being wrong more often → and an exact decoder that meets the deadline removes the need for that trade entirely.
• The awkward half and the expensive half are different halves. The structural phase maintains trees and merges, which suit a processor → the numerical phase grows a budget uniformly, which suits parallel hardware → and profiling shows the time is in the second, so the split captures most of the benefit.
• Distributing global state into per-vertex state is what unlocks hardware. Once each vertex holds enough to act on its own and its neighbours’ condition → one small unit per vertex and per edge becomes possible with only local wiring → which also drops worst-case complexity by a factor of the graph size.
• Independent rare errors make the common case overwhelmingly common. A lone error with nothing adjacent is far more likely than two adjacent ones → resolving that case in hardware in constant time leaves software only the squared-probability event → cutting average processor interactions from proportional to the error rate to proportional to its square.
• Folding rounds in as they arrive removes the wait from the critical path. Decoding a round when it lands rather than batching → means most of the work is finished before the last measurement arrives → so latency becomes roughly independent of how many rounds there were.

What it costs (trade-offs and scope)

• The demonstration is at a code distance no quantum computer has reached. The paper states plainly that the largest surface code reported in physical experiments is distance 7, while the headline result is at distance 13. That is the right way round for a paper anticipating future machines, and it means the result is not yet exercised by real hardware.
• It is not the best decoder everywhere. The paper’s own comparison shows a software decoder winning at very low error rates and small codes, because Micro Blossom runs at a lower clock and includes real interconnect latency, giving it a higher floor. And an approximate Union-Find decoder wins at very high error rates and large codes. Micro Blossom is best in the middle, which is arguably the region that matters, and it is not a clean sweep.
• The scaling ceiling is close. Supporting distance 15 consumes 867,000 of the 900,000 lookup tables on the board. The largest available part would reach distance 31 under the reported scaling. Reaching sub-microsecond latency at distance 15 needs at least 68 MHz, which the paper says is beyond commercially available reconfigurable hardware and would require a custom chip.
• The clock is modest and that is load-bearing. The prototype runs at 62 MHz. The result depends on doing very little work per cycle across very many units rather than on being fast, which is a legitimate design but means headroom comes from a fabrication change rather than tuning.
• The baseline comparison is asymmetric, in the paper’s disfavour. Baseline numbers are processor wall time only, excluding the interconnect latency to the quantum controller, which the paper notes is typically more than 0.8 microseconds by itself. Micro Blossom’s numbers include all of its own interconnect latency. The comparison is therefore conservative, and it is not like-for-like.
• The chosen baseline is not the fastest software decoder. Parity Blossom is used rather than Sparse Blossom, justified on three grounds — the gap between them is about twofold, Micro Blossom is logically equivalent to the former, and the latter’s optimisations are hard to accelerate. The headline eight-times claim against the fastest decoder uses its published numbers on the same processor rather than a re-run.
• The path to larger codes is sketched rather than built. Time-multiplexing units across multiple vertices would relieve the resource ceiling at some latency cost, and the observation that only a constant number of recent rounds matters would cut resource scaling by a factor of the code distance. Both are proposed and neither is implemented.
• One noise model, one code family. Everything is surface codes under a circuit-level noise model with a one-microsecond measurement cycle, and edge weights are quantised to four bits, sufficient for the error rates studied.

The evaluation

Check yourself

Sources

The paper is “Micro Blossom: Accelerated Minimum-Weight Perfect Matching Decoding for Quantum Error Correction” by Yue Wu, Namitha Liyanage and Lin Zhong, published at ASPLOS 2025 Volume 2, pages 639-654, DOI 10.1145/3676641.3716005. All authors are at Yale University. The implementation is open-source and the paper carries an artifact appendix.

This explainer is written from the full text, read through a proxy of the ACM Digital Library copy. Everything above comes from the paper’s own sections 2 through 9: the description of surface codes, decoding graphs with defect and virtual vertices, and the reduction of most-likely-error decoding to minimum-weight perfect matching; the decomposition of the blossom algorithm into primal and dual phases with blossoms, nodes and alternating trees, and the budget-versus-cost intuition for how they negotiate; the profiling showing the dual phase dominating a state-of-the-art software decoder; the argument that decoding latency contributes to the effective logical error rate through idle accumulation, with the distance-21 example where an approximate decoder wins; the heterogeneous architecture with one processing unit per vertex and edge, broadcast and convergecast control networks, and purely local data connections; the complexity improvements from the fourth to the third power of graph size in the worst case and from proportional to the error rate to its square on average; the proof that an isolated error is resolvable in constant time in hardware; round-wise fusion reducing average latency by a further factor of the code distance; the implementation in 2,700 lines of embedded Rust and 4,500 lines of hardware description generating Verilog from a graph description, with a three-stage pipeline; the correctness verification against a known exact decoder; the latency results giving 0.8 microseconds at distance 13 and 0.1% error rate at 62 MHz, the individual contributions of 2.0, 4.2 and 2.0 times combining to 17 times, and the note that baseline numbers exclude interconnect latency while Micro Blossom includes it; the effective error rate comparison showing where a software decoder and an approximate decoder each win; and the scalability analysis of 867 thousand lookup tables at distance 15, the 68 MHz requirement, and the unbuilt proposals for time-multiplexing and constant-round accelerators.