LILLIPUT: a lightweight low-latency lookup-table decoder for near-term Quantum error correction

Quantum error correction needs corrections computed within a microsecond, but accurate decoders run in slow software — LILLIPUT observes that for near-term surface codes every possible error pattern can be enumerated ahead of time, runs the gold-standard matching algorithm offline over all of them, and turns runtime decoding into one FPGA memory read of 29–42 nanoseconds.

The argument in one glance

Problem

Qubits fail a billion times too often, and correction is a race

Quantum hardware errs at roughly 1% per operation; useful algorithms need error rates below 10⁻¹⁰. Quantum error correction (QEC) closes the gap by encoding one logical qubit across many physical qubits and repeatedly extracting parity information (syndromes). A classical decoder must translate each syndrome into corrections within the ~1 microsecond syndrome cycle — or errors pile up faster than they are fixed.
What people did

Accurate software, or fast hardware

The gold-standard decoding algorithm — Minimum Weight Perfect Matching (MWPM) — runs in polynomial time in software, and faster alternatives like Union-Find trade accuracy for speed. Custom hardware decoders and even superconducting logic have been proposed for the latency problem.
Why it fell short

Every experiment so far decoded offline

Software MWPM cannot meet the microsecond budget; fast hardware decoders lose accuracy and are complex to build. So published QEC experiments recorded syndromes and decoded after the fact — fine for characterizing codes, useless for actual fault-tolerant computation, which must correct as it runs. The next milestone, small surface codes with real-time decoding, needed a decoder that is simultaneously accurate, fast, and buildable.
This paper's idea

Precompute every answer; decode with one memory read

For near-term surface codes (distance 3–5), the space of possible error patterns is finite and enumerable. LILLIPUT runs software MWPM offline over every possible detection event, breaks ties using the device’s measured error model, and stores the optimal corrections in a lookup table. At runtime, decoding is a single memory access: 29–42 ns latency, under 7% of an off-the-shelf FPGA, exact MWPM accuracy — and Compressed LUTs cut the memory 107× (148 MB → 1.38 MB) with zero accuracy loss.

Why this problem is worth solving

The site’s Paulihedral explainer covers compiling quantum programs; this paper is about the machinery that must run underneath any future fault-tolerant program: the classical half of

quantum error correction — encoding one logical qubit into many physical qubits (data qubits holding the information, parity qubits measuring checks on their neighbors), so that errors can be detected and undone faster than they accumulate

The leading code is the

a 2D lattice of alternating data and parity qubits, favored because it tolerates relatively high physical error rates and needs only nearest-neighbor connections; its distance d sets the redundancy — a distance-d code can correct roughly (d−1)/2 errors

. Every ~1 microsecond, a syndrome extraction circuit measures all parity qubits, producing a syndrome: a bit per parity qubit, flipping when a neighboring data qubit has erred. A classical decoder must convert syndromes into corrections in real time — before the next syndrome arrives — because deferred corrections mean accumulating errors and, eventually, logical failure.

The status quo was a confession: essentially all QEC experiments decoded offline, storing syndromes and running slow, accurate software afterward. That validates codes but cannot support computation. With hardware approaching the ~1% error rates where distance-3-and-beyond surface codes become functional, the field’s declared next milestone was exactly this: small surface codes with real-time decoding. The decoder for that milestone must hit three targets at once — MWPM-class accuracy, sub-microsecond deterministic latency, and modest enough hardware to sit beside the existing FPGA-based qubit control and readout electronics.

What people did before, and where it broke

Software MWPM.

minimum weight perfect matching — represent detection events as nodes of a decoding graph and pair them (or match them to the lattice boundary) minimizing total weight; the most accurate practical decoding algorithm, running in polynomial time

is the accuracy benchmark, but software implementations miss the microsecond budget by orders of magnitude.

Faster algorithms. Union-Find decodes faster with a different matching strategy — at measurably lower accuracy. In QEC, decoder accuracy is not a soft metric: it multiplies directly into the logical error rate the whole code exists to suppress.

Hardware decoders. Custom microarchitectures and even superconducting-logic decoders attack latency, but implement simplified algorithms (losing accuracy) and add nontrivial engineering burden — a specialized chip next to a dilution refrigerator.

The overlooked regime. All these approaches solve the general problem — decoding codes of any size. But near-term experiments need distances 3–5, where the syndrome is a handful of bits. For a [d=3, m=2] configuration the decoder’s entire input is 8 bits: 256 possible cases. Nobody needs to compute the answer at runtime if every answer can be computed in advance.

LILLIPUT, end to end

Offline: enumerate and solve new

For the chosen configuration [distance d, window m], run software MWPM on every possible detection-event pattern. When MWPM finds several equally-good corrections, use the device error model (Google Sycamore’s) to pick the most probable one. Store each answer — per-data-qubit error assignment plus updated internal state — in a lookup table (LUT).
↓ →
Readout interface → detection events new

Each cycle, XOR the new parity measurements against the previous round: any change is a detection event. Boundary cycles get special handling — the first round compares against initialization values, and the final transversal data-qubit measurement is converted into one last constructed syndrome, so measurement errors at both ends are caught.
↓ →
Sliding-window lookup new

The last m rounds of detection events (plus internal state) form the LUT address; one memory access returns the correction — but errors are assigned only to the OLDEST round in the window before it slides forward one cycle, preventing premature matches that future syndromes would contradict.
↓ →
Error log → logical outcome new

Corrections accumulate in an error log (Pauli frame — no quantum operations needed, just classical bookkeeping). At logical measurement, the log is compared against the measured data qubits to produce the corrected logical result. X and Z errors run through independent parallel decoders.
↓ →
FPGA implementation new

Fully pipelined, 7 clock cycles from syndrome to correction; 29–42 ns total across configurations; under 7% logic utilization on commercial FPGAs (Cyclone 10 LP on-chip for small configs; Arria V with external SRAM/DRAM for larger — or Compressed LUTs to stay on-chip).

Reconfigurable by construction: swap the offline solver, the error model, or the code, and reprogram the table — the runtime hardware never changes.

The idea

Turn an algorithm into an address. The decoder’s input — m rounds of detection events — is a bit string. For near-term codes it is a short bit string, so the entire function “detection pattern → optimal correction” fits in a table. Runtime work collapses to one deterministic memory access, which buys three things simultaneously: latency (29–42 ns, deterministic — no data-dependent matching time), accuracy (the table holds exact MWPM answers, refined by the device error model to break ties — no algorithmic simplification), and simplicity (a memory plus XOR logic and a FIFO, not a matching engine).

Decode a sliding window, commit only the past. Errors are not confined to one cycle: measurement errors create detection events spanning consecutive rounds. LILLIPUT therefore decodes m rounds together, but commits corrections only for the oldest round before sliding forward — a later syndrome may still change the best explanation of recent events, and disjoint windows would cut error chains in half at every boundary. Zero-padding fabricates full windows at the experiment’s time boundaries, and the LUT is programmed so padded regions never receive assignments.

Handle all four error species. A credible decoder must catch errors on data qubits (space-like events), gate errors during syndrome extraction (space-time events), parity-measurement errors (time-like events, appearing and disappearing across rounds), and errors on the final data-qubit measurements. The last is elegant: the transversal logical measurement itself is recycled into one final constructed syndrome, so the decoder’s regular machinery covers the boundary.

Compress by physics, not by generic tricks. Full LUTs grow exponentially with syndrome bits — up to 148 MB for the largest configurations studied, forcing off-chip memory. Compressed LUTs (CLUTs) exploit a property of surface-code errors: a chain of errors flips parity checks only at its endpoints (interior checks flip twice, back to zero), so accessed addresses concentrate at low

the number of 1-bits in a bit string — here, how many detection events fired at once

. CLUTs store only entries up to a cut-off weight, chosen so the probability of missing an entry is at or below the logical error rate itself — making the truncation invisible in the final accuracy. Data-frame layout keeps addressing simple, and the stored entries themselves compress (sparse assignments re-encoded, sliced, Base-Delta- Immediate packed — all offline, in software). Net: up to 107× memory reduction, 148 MB → 1.38 MB, fitting on-chip.

One microsecond in the life of a logical qubit

d = code distance; m = rounds decoded together (window). Syndrome = this cycle's parity-qubit measurements; detection event = XOR of consecutive syndromes. Configuration [d=3, m=2]: 8 detection-event bits form the LUT address. The error walk is illustrative; the pipeline structure and timings are the paper's.

Step 1 of 6

Cycle k: the syndrome arrives

The syndrome extraction circuit (~1 µs) finishes; the readout interface hands LILLIPUT this round’s parity bits. A data qubit erred this cycle, so its two neighboring parity qubits report flipped values.

input: parity measurements, cycle k
budget: correction must land before cycle k+1 completes

Why it works

Near-term codes have tiny syndromes → the full input space (2^address bits) is enumerable → the entire decoding algorithm can run offline, converting runtime computation into one memory access with deterministic latency.
The table stores answers, not algorithms → accuracy equals the offline solver’s (exact MWPM plus error-model tie-breaking) → the usual hardware-decoder trade of speed against accuracy simply does not arise in this regime.
Sliding windows with oldest-round commitment respect error chains’ temporal extent → no premature or boundary-split matches → accuracy is preserved across cycles, including zero-padded time boundaries.
Error chains flip only endpoint checks → accessed addresses cluster at low Hamming weight → truncating the table at a cut-off weight with miss probability ≤ logical error rate compresses 107× at zero accuracy cost — compression justified by physics, not hope.
The runtime is a memory, XORs, and a FIFO → it fits beside existing FPGA control/readout logic → real-time decoding needs no new chip, just a reprogrammable table.

What it costs

Exponential memory, deferred not defeated. LUT size doubles per address bit; beyond distance ~5 the approach is infeasible — LILLIPUT is explicitly a near-term decoder, not a scaling story.
Offline enumeration per configuration. Every [d, m], error model, or code change requires re-running MWPM over the whole input space and reprogramming.
CLUT misses are decoder failures. The cut-off is engineered so their probability sits below the logical error rate — a principled budget, but a budget.
Simulation-based validation. Accuracy comes from Monte Carlo with the standard phenomenological noise model (data plus measurement errors at rate p); the FPGA is synthesized and timed, but no live quantum experiment is decoded in the paper.
Small distances only. Distance 3–5 corrects 1–2 errors; useful fault tolerance eventually needs much larger codes and fundamentally different decoders.

The evaluation

Monte Carlo simulations under the phenomenological noise model (each data qubit errs with probability p per cycle, uniformly X/Y/Z; each parity measurement errs with probability p; p swept from 10⁻³ to 5×10⁻²) over rotated surface codes of distance 3–5, with FPGA synthesis on commercial Intel parts (Cyclone 10 LP, Arria V, Stratix 10).

Decoding options for near-term QEC

Property	Software MWPM (offline)	Prior hardware decoders
Accuracy
Latency vs the ~1 µs budget
Hardware cost	None (a CPU, later)
Window/rounds study	—	—
Scaling ceiling	Polynomial — scales, too slowly

Phenomenological noise model, p = 10⁻³–5×10⁻², rotated surface codes d=3–5, ~5-cycle experiments by default; offline programming via software MWPM with Google Sycamore's error model breaking ties. FPGA results on Intel Cyclone 10 LP (on-chip ≤486 KB), Arria V (external QDR II SRAM / DDR2 for uncompressed large configs), Stratix 10.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

LILLIPUT is validated in simulation with the standard phenomenological noise model, not against a live device — correlated noise, leakage, and crosstalk on real hardware are outside the model. The scaling wall is explicit: table size grows exponentially with syndrome bits, so this is a bridge to the small-code era, not a fault-tolerant endgame (that race — faster general algorithms, streaming hardware MWPM — continues in later work). One typo-level nuance worth knowing: the comparison “CLUT miss probability ≤ logical error rate” bounds accuracy impact statistically, not absolutely. And the 1 µs budget derives from 2021-era superconducting syndrome circuits; the paper shows headroom (400 ns met), but the budget itself is a moving target.

If you remember only three things

1. Real-time decoding is the classical bottleneck of quantum error correction: corrections must land within the ~1 µs syndrome cycle or errors accumulate, yet the accurate algorithm (MWPM) lives in slow software — which is why every QEC experiment before this decoded offline, a mode that can never support actual fault-tolerant computation.
2. For near-term surface codes (distance 3–5) the whole problem is enumerable: run MWPM offline over every possible detection pattern with device-error-model tie-breaking, store the answers, and decode at runtime with one memory access — 29–42 ns, exact-MWPM accuracy, under 7% of an FPGA already sitting in the control stack, with sliding windows and boundary-syndrome construction making it a complete end-to-end system.
3. Compressed LUTs turn a physics fact into 107× memory savings: error chains flip only their endpoint parity checks, so accessed addresses concentrate at low Hamming weight — store only entries below a cut-off whose miss probability is at most the logical error rate, and 148 MB becomes an on-chip 1.38 MB at zero accuracy cost.

Check your understanding

1. LILLIPUT replaces a graph-matching algorithm with a lookup table. Predict the fundamental limit of this move.
2. Compressed LUTs discard most table entries yet lose no accuracy. What makes the discarded entries safe to drop?
3. LILLIPUT decodes m rounds at a time but commits corrections only for the oldest round before sliding forward. What failure does this prevent?
4. Why does a decoder that is merely SLOW (but perfectly accurate) fail quantum error correction, when offline decoding worked fine for every published experiment?