Better Than Worst-Case Decoding for Quantum Error Correction

Gokul Subramanian Ravi, Jonathan M. Baker, Arash Fayyazi, Sophia Fuhui Lin, Ali Javadi-Abhari, Massoud Pedram and 1 other

Fault-tolerant quantum computers must decode error syndromes in real time, but the data grows roughly cubically with code distance — multiple gigabits per second per logical qubit squeezed through a dilution refrigerator's scarce wiring, or decoded inside the fridge under brutal power and thermal budgets — and both options are provisioned for worst-case error patterns that occur under 10% of the time; this paper splits the problem instead, with a Clique decoder of a few logic gates per local neighborhood (0.1–0.3 ns, 10–500 microwatts in superconducting SFQ logic) that corrects the over-90% of syndromes that are trivial AND detects when a case exceeds it, handing rare complex patterns to an off-chip decoder over statistically provisioned bandwidth with execution stalling as the overflow valve — eliminating 70–99+% of off-chip bandwidth at 15–37× less on-chip cost than worst-case cryogenic decoders, with accuracy matching the full decoder.

The argument in one glance

Problem

Error correction produces a firehose of classical data in a freezer

Fault-tolerant quantum computing encodes each logical qubit into hundreds of physical qubits whose ancilla measurements emit classical "syndrome" bits every cycle — bits a classical decoder must interpret in real time to apply corrections (they cannot be deferred past T gates). Per logical qubit the data grows roughly cubically with code distance, reaching multiple gigabits per second. For superconducting machines the qubits sit at millikelvin temperatures inside a dilution refrigerator whose I/O wiring is scarce, heat-leaking, and physically cramped.
What people did

Decode outside the fridge, or inside it

Off-chip decoding runs accurate algorithms (Minimum Weight Perfect Matching) at room temperature — paying the full syndrome bandwidth through the cryostat; AFS adds syndrome compression to soften it. On-chip decoding (NISQ+, QECOOL, XQSim) moves the decoder into the cryogenic domain in superconducting SFQ logic — eliminating the I/O but inheriting the freezer's area, power, and thermal budgets.
Why it fell short

Everyone provisions for the pattern that almost never occurs

Error chains of length k occur with probability ~p^k, and codes are deliberately over-provisioned so complex chains are rare: measured over billions of simulated cycles, over 90% of syndromes are trivial — all-zeros (no error) or isolated single errors with no chains. Yet off-chip pipes carry the full firehose sized for worst-case syndromes; NISQ+ builds worst-case decode logic into the freezer (complex enough that it must approximate, and skips measurement-error handling); and AFS-style compression collapses exactly when syndromes contain non-zero bits, its encoding cost growing with every set bit — while its compressor must itself run cryogenically. Worst-case provisioning taxes every cycle for an event rarer than one in ten.
This paper's idea

A few gates for the common case, a graceful handoff for the rest

This Chicago/USC/IBM collaboration imports Better Than Worst-Case design from classical architecture. The CLIQUE decoder — a handful of combinational gates per local neighborhood, synthesized in cryogenic ERSFQ logic — corrects isolated errors on-chip via a local parity test, and (crucially) DETECTS when a syndrome exceeds its ability, flagging it off-chip to a full MWPM decoder. Two rounds of measurement XOR-filtering absorb transient measurement errors. Off-chip bandwidth is then provisioned STATISTICALLY (e.g., the 99th percentile of complex-decode demand, not the worst case), with a stall cycle — idle gates from the waveform generator — as the overflow valve; provisioning at the average would compound a runaway decode backlog. Results: 70–99+% of off-chip bandwidth eliminated, 10–10,000× more data reduction than AFS compression, 15–37× less power/area than NISQ+ at 0.1–0.3 ns latency, with logical error rates matching the full decoder.

Why this problem is worth solving

the machinery that makes long quantum computations possible despite noisy hardware: each logical qubit is encoded across many physical data qubits, with interleaved ancilla qubits repeatedly measured to produce classical SYNDROME bits that fingerprint errors without collapsing the data. A classical decoder reads each cycle’s syndrome, infers which physical errors most likely occurred, and applies corrections — done accurately, this drives logical error rates orders of magnitude below physical ones

is the toll bridge every long-term quantum ambition must cross — Shor-scale factoring needs logical error rates near one in a trillion from hardware that errs once in a thousand operations. The leading code family,

codes that arrange data and ancilla qubits in a 2D nearest-neighbor lattice — matching real superconducting chips — with a CODE DISTANCE d setting the redundancy: physical qubits per logical qubit grow as d², and the shortest uncorrectable error chain has length d. A distance-15 code spends roughly 500 physical qubits per logical qubit; the syndrome stream grows as d² per round, times d rounds against measurement noise

, makes the decoding load concrete: multiple gigabits per second of syndromes per logical qubit, every cycle, forever.

For transmon machines the geography is cruel: qubits live at 20 millikelvin, decoders either outside (through I/O wiring that leaks heat into a fridge with ~1 watt of cooling at 4 K, and physically cannot scale per-qubit coax to thousands of qubits) or inside, built from

Single Flux Quantum — classical logic in superconducting hardware, switching in ~1 picosecond at ~100 attojoules, orders of magnitude below cryo-CMOS. The catch: every gate spends Josephson junctions and microwatts inside the thermal budget, so cryogenic circuit complexity is a scarce resource

. The paper’s reframing is that this brutal either/or is an artifact of worst-case thinking: the syndromes that actually arrive are overwhelmingly trivial because the code was over-provisioned to make complex errors rare. The redundancy that guarantees correctness also guarantees a common case — and nobody was harvesting it.

What people did before, and where it broke

Off-chip MWPM (software, FPGA, ASIC). Minimum Weight Perfect Matching finds the most probable error configuration — accurate, mature, and room-temperature. But the full syndrome stream crosses the cryostat: gigabits per second per logical qubit against scarce, heat-leaking wiring; a thousand logical qubits is out of the question.
AFS with syndrome compression. Compress before transmitting — effective for all-zero syndromes (one bit), but the sparse encoding costs ~1 + O(k·log N) bits for k non-zero entries, eroding quickly with real errors; the compressor itself must run cryogenically (no hardware implementation given); and it defers, rather than performs, every decode.
On-chip worst-case decoders (NISQ+, QECOOL, QULATIS, XQSim). Full decoding in SFQ inside the fridge — zero off-chip bandwidth, but the worst-case logic is so costly that NISQ+ must approximate and omits measurement-error correction, and its power/area (37×/25× Clique’s at distance 9) caps how many logical qubits a 1-watt cooling budget can host.
The shared blind spot. All provision every cycle for syndromes that occur in well under 10% of cycles — and the fraction shrinks further as hardware improves, since chains become ever rarer relative to isolated errors.

How BTWC decoding works

Split by difficulty, hand off by self-diagnosis

The trivial/complex split (measured, not assumed)

Monte Carlo over billions of cycles: syndromes are ALL-0s (no error), LOCAL-1s (isolated errors, no chains of length 2+), or COMPLEX (chains). Across practical physical/logical error rate combinations, All-0s + Local-1s exceed 90% — because k-error chains scale as p^k and code distance is chosen precisely to make them rare. The common case is a mathematical consequence of the code's own over-provisioning.
↓ →
Clique decoder: one parity test per neighborhood new

For each ancilla 'a' with neighbor ancillas p,q,r,s and adjacent data qubits w,x,y,z (a "clique"): if a fired and the neighborhood parity of {p,q,r,s} is ODD, the error is an isolated data-qubit error — correct the data qubit shared with the fired neighbor (a&&p → fix w, etc.), exactly the minimum-weight choice MWPM would make. If a fired with EVEN neighborhood parity, a chain (or persistent measurement error) is afoot: flag COMPLEX, send off-chip. Every decision is local to a clique — no global communication — and overlapping cliques' corrections combine by simple ANDs.
↓ →
Measurement-error filtering new

Ancilla measurements themselves err. Clique XORs syndromes across two consecutive rounds: flips that vanish next round are transient measurement errors (or self-corrected) and are ignored; flips that persist are treated as real. Lone persistent flips with no pairable neighbor read as complex and go off-chip. More rounds can be added for accuracy at modest hardware cost.
↓ →
Cryogenic implementation new

Verilog, synthesized to the ERSFQ cell library (path-balanced, Josephson-junction-counted). Per logical qubit: 10–500 microwatts (distance 3→21), under 100 mm² even at distance 21, latency 0.1–0.3 ns regardless of input. A 1 W @ 4 K fridge could host ~2,000 logical qubits at distance 21 — or 100,000 at distance 3.
↓ →
Statistical off-chip bandwidth allocation new

Complex decodes still cross the fridge — but now only ~1–30% of cycles per qubit. Provisioning for the AVERAGE demand fails catastrophically: any overflow stalls a cycle, the stall itself breeds new errors, and carryover-plus-new demand exceeds average forever — a runaway backlog (90+ stalls per 100 cycles simulated). Provisioning at the 99th percentile (~30% above average) clears every backlog promptly. Saved bandwidth is not idle wire — it hosts more logical qubits.
↓ →
Decode-overflow execution stalling new

When a cycle's complex-decode count exceeds provisioned bandwidth, a control signal makes the waveform generator issue Identity gates — one stall cycle — letting off-chip decoding catch up before further gates commit. Errors still accrue during stalls, which is exactly why provisioning must beat the average: the valve works only if backlogs shrink.

Evaluation: Monte Carlo lifetime simulation (a billion cycles per logical qubit; a million cycles × 1,000 logical qubits for bandwidth studies), phenomenological noise model (data and measurement errors, probability p each), MWPM as the complex-case and comparison decoder; physical error rates 5E-3 to 5E-4, logical targets 1E-5 and 1E-12, distances 3–21.

The idea

The code’s over-provisioning guarantees a common case — harvest it. Correction codes are sized so that the error patterns they cannot handle are vanishingly rare; a side-effect nobody exploited is that patterns which are hard-but-possible are nearly as rare. The measured distributions make it precise: over 90% of syndromes are all-zeros or isolated errors whose minimum-weight interpretation is unambiguous. Worst-case decoders spend their silicon and bandwidth re-deciding this triviality every cycle with full machinery. The BTWC split pays the heavy machinery only when heaviness is present — and the economics improve with progress, since better qubits make chains rarer still.

A cheap fast path is safe only if it knows its own limits. The Clique decoder’s load-bearing property is not that it corrects isolated errors (any lookup could) but that its parity test detects incapability: even neighborhood parity means the local picture is inconsistent with an isolated error, so the syndrome must involve a chain or persistent measurement fault — punt off-chip. The test is local (no clique needs to see the lattice), constant-latency, and errs toward deference; the logical-error evaluation confirms Clique+MWPM matches MWPM alone at distances 3–7, with only a marginal gap at 9–11 traceable to the two-round measurement window (widenable at trivial cost, given 37× headroom). This site’s fast-path pages — a switch aggregating what it can, a page-table fallback, an NPU offload — all live or die on the same property: the cheap path must never silently mishandle what belongs to the slow path.

Provision the pipe for the tail, and buy a valve. Once the common case is filtered on-chip, off-chip demand becomes a random variable with a thin tail — and the paper is careful about a trap this site’s queueing-minded readers will recognize: provisioning for the mean of a stochastic demand with feedback (stalls create errors, errors create demand) diverges. The 99th-percentile allocation costs ~30% more wire than the mean and converts an unbounded backlog into isolated single-cycle stalls; the stall mechanism itself is a one-signal Identity-gate insertion. The tradeoff is then a dial the user reads off a curve: tolerate 10% execution-time overhead and keep 8.5–150× bandwidth reduction — fidelity, not speed, being the currency of fault tolerance.

One decode cycle, four fates

A distance-9 logical qubit, 20 millikelvin, one cycle

Clique = ancilla a + neighbor ancillas p,q,r,s + adjacent data qubits. Parity test = is the count of fired neighbors odd? Numbers from the paper's simulation and ERSFQ synthesis.

Step 1 of 6

Syndromes arrive, twice

All ancillas are measured; the Clique hardware XORs this round against the previous one. A flipped ancilla that reverts next round is dismissed — a transient measurement error or self-corrected blip, no action. Only persistent flips proceed. This two-round filter is the entire measurement-error defense, in a few gates per ancilla.

NISQ+ omits measurement-error handling entirely to fit its budget
more rounds are affordable if needed: Clique has 37× power headroom vs NISQ+

Why it works

Chains of k errors occur with probability ~p^k and distance is chosen to make long chains vanishingly rare → the same over-provisioning that guarantees correctness guarantees that over 90% of syndromes are trivial → a decoder sized for triviality is right most of the time by construction.
An isolated error’s minimum-weight interpretation is locally decidable (odd neighborhood parity around a fired ancilla) → a few combinational gates per clique reproduce MWPM’s answer exactly on trivial cases, in constant 0.1–0.3 ns, with no cross-lattice communication → cryogenic cost collapses by 15–37×.
Even parity is locally detectable too → the fast path self-diagnoses incapability and defers, never silently mis-decoding a chain → accuracy tracks the full decoder, and the rare-case machinery is exercised only when rareness actually arrives.
Two-round XOR filtering exploits the temporal signature of measurement errors (they do not persist) → most measurement noise dies on-chip in gates, not decoders → the main prior on-chip design simply omitted this class.
Filtered off-chip demand is a thin-tailed random variable, but stalling feeds back into demand → percentile (not mean) provisioning keeps the backlog contractive → a 30% wire premium converts divergence into isolated stalls, and unused lanes host more logical qubits.

What it costs

A marginal accuracy gap at high distance. With two measurement rounds, coordinated sticky measurement errors can masquerade as trivial: logical error rates trail MWPM slightly at distances 9–11. More rounds close the gap — affordable given the 37× power headroom — but are not in the baseline design.
The worst case still needs the worst-case machinery. Clique eliminates bandwidth, not the off-chip decoder: MWPM (or successor) must exist, be fast, and be reachable; BTWC is a filter, not a replacement.
Stalls are real slowdown. Aggressive bandwidth minimization diverges; practical operating points give back 1.25–2× of the maximum reduction to keep stalls near 10% of execution time — a curve that must be re-analyzed per error rate and distance.
Simulation, phenomenological noise. No hardware today runs fault-tolerant workloads; all results are Monte Carlo under an idealized noise model (uniform, uncorrelated p for data and measurement errors), and ERSFQ synthesis numbers are pre-fabrication.
Surface-code specificity. The parity test leans on surface codes’ locality; LDPC-family codes have sparsity but not necessarily locality (the authors sketch extensions), and color codes remain future work.

The evaluation

Billion-cycle Monte Carlo per configuration across six physical/logical error-rate regimes and distances 3–21; thousand-qubit bandwidth simulations; ERSFQ logic synthesis with a published cell library; direct quantitative comparison to the state-of-the-art on-chip decoder (NISQ+) and off-chip compression (AFS).

Where to put the decoder, and what to size it for

Property	Off-chip worst-case (MWPM; AFS + compression)	On-chip worst-case (NISQ+ family)
Cryostat I/O bandwidth		None — everything decoded in the fridge
Cryogenic resource cost	Compression hardware unspecified — and must itself run cryogenically
Accuracy (logical error rate)	MWPM: the reference standard	Approximate by necessity; no measurement-error correction
Worst-case behavior	Bandwidth sized for it — every cycle pays	Logic sized for it — every joule pays; NISQ+ worst-case latency 6× its own average
Operating flexibility	Fixed pipe	Fixed silicon

Noise: phenomenological model, equal data/measurement error probability p ∈ {5E-3, 1E-3, 5E-4}; logical targets 1E-5 (near-term) and 1E-12 (Shor-scale); distances 3–21. Synthesis: ERSFQ cell library (Josephson-junction counts per gate), SFQMap-based flow. Coverage: ~70% on-chip at the hardest point (p=1%, d=21) rising toward 100%; near threshold, nearly all NON-zero syndromes still resolve on-chip.Underlined values explain themselves when clicked.

Background

The fast path that knows its limits, at 20 millikelvin

This page joins the site’s quantum cluster — compiler, control-hardware, and ansatz pages covered elsewhere on this site — as its fault-tolerance entry, and it is simultaneously the purest specimen yet of a pattern the classical pages keep rediscovering: the best-effort fast path with self-diagnosed fallback. A switch aggregates the tuples it can and forwards the rest; a flattened page table falls back to 4 KB nodes; an on-chip parity test corrects isolated errors and defers chains. In every case the load-bearing property is the same — the cheap path must detect, not guess at, its own limits — and here the stakes are highest, since a silent mis-decode corrupts a logical qubit. The provisioning half tells a queueing story this site’s serving pages know well: mean-provisioning a stochastic demand with feedback diverges, and a modest tail premium buys stability. That both lessons transfer unchanged from datacenters to dilution refrigerators is the strongest kind of evidence that they are laws, not idioms.

If you remember only three things

1. Real-time surface-code decoding faces a geographic dilemma — gigabits per second of syndromes per logical qubit through a dilution refrigerator's scarce, heat-leaking I/O, or worst-case decode logic inside the fridge's watt-scale power budget — and every prior solution provisions both for complex chained errors that constitute under 10% of syndromes, because k-error chains scale as p^k and codes are deliberately over-provisioned to make them rare.
2. BTWC decoding splits by difficulty with a self-diagnosing fast path: the Clique decoder's local parity test (a few ERSFQ gates per ancilla neighborhood, 0.1–0.3 ns, 10–500 µW per logical qubit) corrects isolated errors with exactly MWPM's minimum-weight answer, filters transient measurement errors by two-round XOR, and — crucially — detects chains as locally inconsistent (even parity) and defers them off-chip rather than ever guessing; statistical 99th-percentile bandwidth provisioning plus Identity-gate stall cycles keep the off-chip backlog contractive where mean-provisioning would diverge into permanent stalling.
3. The result eliminates 70–99+% of off-chip bandwidth (10–10,000× beyond AFS compression, which helps only near-empty syndromes) at 15–37× less cryogenic cost than worst-case on-chip decoding, with logical error rates matching full MWPM at distances 3–7 — supporting ~2,000 distance-21 logical qubits per watt of 4 K cooling — while honestly costing a marginal accuracy gap at distances 9–11, a per-system bandwidth/stall tuning curve, and simulation-only evidence under idealized noise.

Check yourself

Check your understanding

1. The paper's foundation is that over 90% of error syndromes are trivial. Predict why this is guaranteed rather than lucky — and what happens to the fraction as quantum hardware improves.
2. The Clique decoder is a handful of gates, yet pairing it with MWPM loses essentially no accuracy at distances 3–7. What single property of the design makes the cheap path safe — and where does the measured exception at distances 9–11 come from?
3. With Clique filtering 95% of decodes, why does provisioning off-chip bandwidth for the AVERAGE residual demand fail catastrophically — and what does percentile provisioning fix?
4. AFS also reduces off-chip bandwidth, by compressing syndromes before transmission — yet Clique achieves 10–10,000× more data reduction. Why does a tiny DECODER so thoroughly beat a COMPRESSOR?

Sources

arXiv preprint 2208.08547 — full text
ACM DL: Better Than Worst-Case Decoding for Quantum Error Correction — ASPLOS 2023 (open access)