Promatch: Extending the Reach of Real-Time Quantum Error Correction with Adaptive Predecoding

Narges Alavisamani, Suhas Vittal, Ramin Ayanzadeh, Poulami Das and Moinuddin K. Qureshi

A quantum computer has to work out what went wrong and fix it within a microsecond, every microsecond, or errors pile up faster than they can be cleared — and the exact algorithm for doing that only fits in the budget for small codes, which is a problem because small codes are not reliable enough to be useful. This paper (Georgia Tech and UT Austin) inserts a fast pre-pass that clears away the easy errors first, and finds that the trick is knowing which easy match to make, because pairing two bits carelessly can strand a third with nowhere local to go.

The argument in one glance

Problem

The correction has to be computed before the next one arrives

A fault-tolerant quantum computer spends its life measuring parity checks and asking a classical computer which qubits went wrong. That question has a deadline of roughly one microsecond on superconducting hardware, because the next round of measurements is already on its way and any delay compounds into a backlog that never clears. The useful applications need error rates below one in a trillion, which means large codes, which means more parity checks failing at once — so the deadline gets harder exactly as the requirement gets stricter.
What people did

Implement the exact algorithm in hardware

There is a gold-standard answer: treat the failed parity checks as nodes in a graph, weight the edges by how likely each error chain is, and find the pairing of minimum total weight. Software implementations are far too slow for a microsecond, so recent work built it directly in hardware, brute-forcing every possible pairing. That works, and it is exact — the state of the art handles up to ten failed checks, which covers surface codes up to distance 9.
Why it fell short

The number of pairings explodes, and the codes that matter are bigger

Ten failed checks already means 945 possible pairings, and the count grows exponentially with each additional one, so brute force stops being viable almost immediately. Past distance 9 the number of simultaneously failed checks routinely runs well beyond ten. The workaround is to decode greedily instead of exactly, which fits in the budget but gives up accuracy — at distance 13 the greedy real-time decoder produces a logical error rate 43 times worse than the exact algorithm would.
This paper's idea

Clear the easy errors first, but only the ones you are sure about

This paper (Georgia Tech and UT Austin — Alavisamani, Vittal, Ayanzadeh, Das and Qureshi) puts a fast pre-pass in front of the exact decoder, matching obvious pairs and removing them so that what remains fits the exact decoder budget. Predecoding has been tried before and always broke on the same trade-off: cover enough and you make mistakes, be careful and you do not cover enough. The insight here is that the danger is specific and predictable — a careless match can leave a third bit with no local partner — so the pre-pass can be ordered from safest to riskiest and stopped as soon as the deadline permits.

Why this problem is worth solving

The computation being raced against a deadline is a graph problem, and its shape explains the deadline.

A SURFACE CODE spreads one logical qubit across a grid of physical ones — for code distance d, that is d squared data qubits plus one fewer parity qubits. The parity qubits are measured continuously, and a failed check means an error happened nearby. The pattern of failed checks is called the SYNDROME, and turning it into a correction is a graph problem: build a graph whose nodes are the failed checks and whose edges are weighted by how probable the corresponding error chain is, then find the PERFECT MATCHING of minimum total weight, since the likeliest explanation is the fewest and most probable errors. One complication doubles the size: the measurements are themselves faulty, so the decoder must consider d consecutive rounds together rather than one snapshot, which is why the graph is three-dimensional and the failed checks accumulate

The deadline and the algorithm’s cost point in opposite directions.

Decoding has to finish in about a microsecond on superconducting hardware, because the next syndrome is already arriving and a backlog grows without bound. Software implementations of the exact algorithm cannot come close, so the fast decoders are built directly into hardware — and the way they achieve exactness is by trying every possible pairing. The count of pairings is what kills this. Ten failed checks, referred to as a HAMMING WEIGHT of ten, already admit 945 distinct pairings, and each additional failed check multiplies that further, so the brute-force approach stops scaling past distance 7 and a more selective variant reaches distance 9. The trouble is that the number of simultaneously failed checks grows with the code, so exactly when larger codes become necessary for low error rates, the syndromes stop fitting the decoder that could handle them accurately

What people did before, and where it broke

Precompute every possible correction into a lookup table. For small codes this reduces decoding to a single memory read of a few dozen nanoseconds.
But the table grows exponentially. It works for near-term distances and has no path to the distances that reach useful error rates.
Brute-force the exact matching in hardware. This is genuinely exact and fast enough, handling syndromes up to ten failed checks.
But ten failed checks is already 945 pairings. The count explodes with each extra check, so this covers distance 7, and a greedier variant reaches 9.
Decode greedily and accept the loss. Match failed checks in a plausible order until the rest is small enough, which guarantees the deadline is met.
But the accuracy cost compounds with distance. At distance 11 the greedy decoder is 2.5 times worse than exact matching, and at distance 13 it is 43 times worse.
Predecode only the patterns you are certain about. Match isolated pairs and pass anything complicated to the main decoder untouched.
But that leaves the main decoder with the hard part. One such predecoder cannot improve the main decoder’s error rate at all, because it never removes enough to change what the main decoder faces.
The gap. Every predecoder had picked a side of the same trade-off. Cover aggressively and the mistakes you make land straight in the logical error rate; cover cautiously and the syndrome arriving at the main decoder is still too big.

How a pre-pass learns which matches are safe

Turning a syndrome too large to decode exactly into one that fits the deadline

Send the whole syndrome to an exact hardware matcher

Build the graph of failed parity checks and find the minimum-weight pairing by considering every possibility. This is the established real-time approach and it is exact, but the number of pairings grows so fast that it only works while the syndrome stays small.
↓ →
Put a fast pre-pass in front of it new

Match some failed checks to their obvious neighbours and remove them from the graph, so the main decoder sees a smaller problem. This idea is not new either, and it has always foundered on the same tension: every match the pre-pass gets wrong lands directly in the final error rate.
↓ →
Name the specific way a careless match hurts new

The danger is creating a SINGLETON — a failed check whose only neighbour just got matched to somebody else, leaving it with no local partner. It must then be paired across a long chain, which is improbable, so the total weight of the solution rises. The rule that follows is simply never to create one.
↓ →
Order the moves from safest to riskiest new

Start with pairs that are isolated, where the two checks are each other only option. Then pairs that can be matched without stranding anyone, preferring a check that has just one neighbour and otherwise the most probable link. Then deal with existing singletons. Only last, and only if forced, make a match that creates one.
↓ →
Stop as soon as what remains fits the time left new

Do not predecode a fixed amount. Track how much of the microsecond is gone, check whether the remaining failed checks are within what the exact decoder can finish in the time that is left, and stop the moment they are. Every match beyond that point is risk taken for no benefit.
↓ →
Run the greedy decoder alongside and keep the better answer new

The pre-pass plus exact decoder and the standalone greedy decoder fail on different syndromes, so run both in parallel and compare the total weight of the two solutions at the end. Taking whichever is lighter recovers the remaining gap to what offline exact matching would have produced.

Evaluated on surface codes of distance 11 and 13 across physical error rates from 1 to 5 in ten thousand, with an FPGA implementation running at 250 megahertz.

The idea

The trade-off was not a law, it was a missing distinction. Predecoding had been tried repeatedly and always landed on one horn or the other: aggressive schemes covered enough of the syndrome but their mistakes went straight into the logical error rate, while conservative schemes only touched patterns they were certain about and consequently removed too little to help — one of them cannot improve its main decoder’s error rate at all. The paper’s contribution is to observe that the risk in a match is not diffuse but concrete and checkable. Pairing two neighbouring failed checks is dangerous specifically when it strands a third one, leaving it with no adjacent partner and forcing it to be matched across a long chain that is far less probable, which raises the weight of the whole solution and can flip it to the wrong answer. Once that is named, the algorithm falls out as a priority order: isolated pairs first because they can never strand anyone, then matches that provably create no singleton, then singletons that already exist, and only in extremis a match that makes one. Replacing a vague sense that some choices are riskier with a specific structural condition you can test for is the same name-the-failure-mode move covered elsewhere on this site where a heuristic becomes principled once somebody identifies exactly what it was implicitly guarding against.

Do exactly as much of the easy work as the deadline requires, and no more. The second idea is that the amount of predecoding should not be a design constant. Too little and the main decoder cannot finish; too much and you have taken accuracy risk for capacity you did not need. So the pre-pass is adaptive: it tracks the remaining time budget and stops the moment the residual syndrome is small enough for the exact decoder to complete within it. That is what makes the priority ordering pay off, because the riskiest steps only ever run when the safe ones have not yet done enough — and the measurements show how rarely that is. At distance 13, 99.83 percent of syndromes are handled entirely by the first and safest step. The authors then make an argument that is easy to skip past and is the sharpest thing in the evaluation: the last and riskiest step is still invoked more often than the target logical error rate, so it cannot be dropped, because anything that happens more frequently than the error rate you are chasing determines that error rate. Spending a scarce budget on the common case while keeping a rare expensive path because rare is still more often than the target failure rate is the same pay-for-the-common-case-but-keep-the-tail structure covered elsewhere on this site where a system provisions for typical behaviour and retains a fallback precisely because the tail is what the guarantee is made of.

Two decoders that fail differently are better than either alone. The final configuration is almost embarrassingly simple and works because the failure modes are complementary. The pre-pass followed by exact matching is strong on syndromes that decompose into local structure, while the standalone greedy decoder handles some dense cases better; each has syndromes it gets wrong that the other gets right. So run them concurrently, compare the total weight of the two candidate solutions, and keep the lighter one — which is a well-defined comparison, since weight is exactly what the problem is minimising. That recovers essentially all the remaining gap: at distance 13, where the greedy decoder alone is 43 times worse than offline exact matching and the pre-pass alone is about 8 times worse, the pair together matches it. Running two approximations with uncorrelated blind spots and selecting between them by the objective they share is the same ensemble-with-a-real-tiebreaker structure covered elsewhere on this site where two imperfect strategies combine cleanly because the metric that ranks them is available at runtime.

Watching a syndrome get cut down to size

From more failed parity checks than any exact decoder can handle to a correction, inside a microsecond

All figures from the paper, for surface codes of distance 11 and 13 at a physical error rate of one in ten thousand.

Step 1 of 5

A syndrome arrives that is simply too big

The parity checks report their failures across many rounds, and the count exceeds what an exact hardware matcher can consider. Ten failed checks already admit 945 possible pairings and the number grows exponentially, so the exact decoder covers distance 7 and a more selective variant reaches 9. At distance 13 this is routine, not exceptional.

the deadline is about one microsecond on superconducting hardware, because the next syndrome is already arriving
falling behind is not a slowdown but a divergence, since the backlog grows without bound

Why it works

A careless match strands a third failed check with no adjacent partner → that check must then be paired across a long, improbable chain → so forbidding matches that strand anyone directly protects the weight of the final solution.
Isolated pairs cannot strand anything and leaving them unmatched risks stranding both → taking them first is unconditionally safe → and it turns out to be enough on its own for 99.8 percent of syndromes.
The right first match inside a tangled cluster decomposes it into simple ones → two probable matches replace one improbable chain → so the pre-pass gets safer as it proceeds rather than more dangerous.
Predecoding more than necessary buys capacity that is not needed and spends accuracy → stopping the instant the residual fits the remaining time → means risky steps only run when the safe ones have genuinely fallen short.
The pre-pass and the standalone greedy decoder fail on different syndromes → both produce a solution with a well-defined total weight → so running them concurrently and keeping the lighter answer recovers what either alone would lose.

What it costs (trade-offs and scope)

Accuracy still degrades with physical error rate. Across the sweep, the pre-pass alone stays within about 6 times the exact algorithm at distance 11 but drifts to 202 times at distance 13, and only the paired configuration stays close.
The good result needs two decoders running at once. Matching the exact algorithm at distance 13 requires the pre-pass, the exact matcher and the greedy decoder concurrently, which is real hardware area and power.
Precomputed tables grow with distance. Path weights need 129 kilobytes at distance 11 and 345 at distance 13, compressed by bucketing paths into four groups since exact weights turn out not to matter.
The reach extends to 13, not indefinitely. Every mechanism here pushes the same wall further out rather than removing it, and useful computation is generally expected to need larger distances still.
Uniform noise, simulated. Every physical error is assumed equally likely and results come from a standard simulator over millions of trials, which is the field norm but is not a measurement on hardware.

The evaluation

Surface codes of distance 11 and 13, simulated over millions of trials at physical error rates from one to five in ten thousand, using a standard circuit-level noise model where every operation fails with the same probability. Comparisons cover the three positions on the accuracy-coverage trade-off: an exact hardware matcher, a greedy real-time decoder, a conservative predecoder that only touches simple patterns, and an aggressive one that maximises coverage. The reference throughout is offline exact matching, which is too slow to run in real time but defines what accuracy is achievable at all.

Property	Conservative predecoding	Greedy real-time decoding	Adaptive predecoding
How much of the syndrome it clears
Error rate at distance 13
How risk is controlled
What runs in the common case
Largest distance handled in real time

At distance 13 and a physical error rate of one in ten thousand, offline exact matching reaches a logical error rate of 3.4 in a thousand trillion; the greedy real-time decoder reaches 1.4 in ten trillion, 43 times worse; the adaptive pre-pass with an exact matcher reaches 2.6 in a hundred trillion, 5.6 times better than greedy; and running both concurrently matches offline exact matching. The conservative predecoder paired with an exact matcher is worse by a factor of over a billion, because it never removes enough for that matcher to run at all.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The headline claim of matching exact-matching accuracy at distance 13 belongs to the paired configuration, not to the predecoder alone: it requires the pre-pass, the exact hardware matcher and a separate greedy decoder all running concurrently, with a comparison at the end. The pre-pass on its own is about 8 times worse than the exact algorithm at that distance, which is a real improvement over the 43 times of the greedy decoder but not the same thing. Accuracy also degrades as physical error rates rise: across the sweep, the pre-pass alone drifts to 202 times the exact algorithm at distance 13, and even the paired configuration reaches 14 times, so the best-case numbers describe the lowest error rate tested. Costs scale too, with precomputed path weights growing from 129 to 345 kilobytes between distance 11 and 13, compressed by discovering that exact path weights do not matter and four buckets suffice. And the scope should be read as pushing a wall rather than removing it — this extends real-time exact-quality decoding from distance 9 to 13, where useful computation is generally expected to need more still, and every mechanism involved becomes harder as syndromes grow. Finally, all of this is simulation under a uniform noise model where every operation fails with equal probability, which is the standard assumption in the field but is not the same as a measurement on a machine.

Background

When the exact answer does not fit the deadline

This paper sits in the site’s quantum cluster and rhymes with several ideas covered elsewhere on this site. Its closest sibling is the better-than-worst-case decoding page, which splits the same problem the same way — a cheap path sized for what usually happens plus a fallback for what occasionally does — and reaches the same conclusion that provisioning uniformly for the worst case wastes a budget that could buy accuracy elsewhere. It is also the direct successor to the lookup-table decoder page, which achieves nanosecond decoding by precomputing every possible answer and works precisely as long as the code is small enough for that table to exist; both are attempts on the same wall from opposite sides. Its central discipline, of naming exactly what makes a greedy choice dangerous instead of treating riskiness as a matter of degree, rhymes with the pages where a heuristic becomes defensible once its implicit assumption is written down. And its argument that a step invoked far less than one percent of the time still cannot be removed, because it happens more often than the failure rate being targeted, is the same rare-events-define-the-guarantee reasoning the tail-latency and reliability pages rely on.

If you remember only three things

1. A fault-tolerant quantum computer must turn each round of parity measurements into a correction within about a microsecond, or the backlog grows without bound. The accurate method treats failed checks as graph nodes and finds the minimum-weight pairing, and hardware implementations achieve that exactly by trying every possibility — but ten failed checks already admit 945 pairings and the count explodes from there, so exact real-time decoding stops at distance 7, and a selective variant at 9. Larger codes are exactly what low error rates require, and they produce more simultaneous failures, so the decoder runs out of capacity precisely where it is needed.
2. A pre-pass that clears easy errors first is an old idea that kept failing on one trade-off: cover enough of the syndrome and your mistakes land in the final error rate, be careful and you remove too little to help. The contribution here is naming the danger precisely. Matching two adjacent failed checks is risky exactly when it STRANDS a third, leaving it with no local partner so that it must pair across a long, improbable chain that inflates the solution weight. From that condition an ordering follows: isolated pairs first, then matches that strand nobody, then already-stranded checks, and only in extremis a match that creates one.
3. The pre-pass is adaptive rather than fixed, stopping the instant the residual fits what the exact decoder can finish in the time remaining, so risky steps only run when safe ones have fallen short — and at distance 13 the safest step alone suffices for 99.83 percent of syndromes. The sharpest argument in the paper is why the rarest step survives anyway: it is invoked more often than the target logical error rate, and anything more frequent than the error rate you are chasing determines it. Run this alongside a greedy decoder, compare solution weights and keep the lighter, and distance 13 decodes in real time at the accuracy of the offline exact algorithm.

Check yourself

Check your understanding

1. Exact matching decoders are already implemented in hardware and meet the microsecond deadline. Predict why they do not simply get used for larger codes.
2. Predecoding has been tried before and always hit the same wall: cover enough and you make mistakes, be careful and you clear too little. Predict how this work escapes it.
3. The safest step of the algorithm handles 99.83 percent of syndromes at distance 13. Predict the paper argument for keeping the rarest and riskiest step anyway.
4. The final configuration runs the predecoder-plus-exact-matcher and a standalone greedy decoder at the same time. Predict why that combination is worth the extra hardware.

Sources

Narges Alavisamani, Suhas Vittal, Ramin Ayanzadeh, Poulami Das and Moinuddin Qureshi. “Promatch: Extending the Reach of Real-Time Quantum Error Correction with Adaptive Predecoding.” ASPLOS 2024, Volume 3. Georgia Tech and the University of Texas at Austin. DOI 10.1145/3620666.3651339. Preprint at arXiv 2404.03136.
Full text of the paper was used for this explainer, including the surface code and decoding background and the survey of prior predecoders in Section 2, the locality-aware greedy algorithm and its four prioritised steps in Section 4, the hardware pipeline and comparison with earlier predecoders in the same section, the noise model and simulation setup in Section 5, and the logical error rate results, sensitivity sweep, step usage frequencies and resource requirements in Section 6.