Backlog Metastability in Windowed Quantum Error Correction Decoding
- 1. Cognitive Fab LLC, USA
Abstract
Real-time quantum error correction requires a classical decoder to consume syndrome measurements at the rate the quantum hardware produces them, roughly one round per microsecond on superconducting devices. The standard stability requirement is a utilization condition: the mean decode time per round must be less than the round period, ρ < 1. We show that this condition is inadequate for windowed decoders whose per-window cost grows superlinearly in the number of detection events, which is the empirical shape of matching-based decoders under burst-like syndrome content. For this class, stability is not a threshold but a basin. The deterministic backlog dynamics have a stable operating point and an unstable boundary B*. Noise erodes that boundary downward, and sufficiently superlinear decoders escape spontaneously. In discrete-event simulations paired under common random numbers, a decoder with cost exponent γ = 1.5 and mean utilization ρ0 = 0.6 (forty percent nominal headroom) fails without provocation, with a mean time to failure of 1,344 ± 289 rounds, about 1.3 ms of wall clock at a 1 µs cycle. We measure the cost exponent of a production decoder (PyMatching 2, sparse blossom) and find it anisotropic: near-linear (γ ≈ 1.1–1.2) when a window grows in length at fixed syndrome density, but approximately quadratic (γ ≈ 2) when the same window grows denser. Bursts travel along the dangerous axis, where the basin is 2–4 rounds deep for ρ0 between 0.5 and 0.8. Spatially clustered event content, the syndrome footprint of leakage and cosmic-ray bursts, is worse still: at matched event count, clustered windows cost 7.6× length-grown ones and 4.8× uniformly densified ones, so the quadratic density exponent is a conservative proxy for burst content. Greedy catch-up (“decode everything queued”) is precisely the divergent policy. A bounded decoding window restores stability, and the measured stability edge lands on a closed-form line. The simulation model is cross-validated against Stim at the level of individual fault mechanisms.
Keywords
• Surface Code; Real-Time Decoding; Minimum-Weight Perfect Matching; Fault-Tolerant Quantum Computing; State-Dependent Queues; Stochastic Stability; Correlated Error Bursts; Discrete-Event Simulation
Citation
Dubray JJ (2026) Backlog Metastability in Windowed Quantum Error Correction Decoding. Comput Sci Eng 5(1): 1017.
INTRODUCTION
A fault-tolerant quantum computation is a race between two processors. The quantum hardware emits syndrome measurements on a fixed cadence, and a classical decoder must convert them into corrections fast enough for the computation to proceed. If decoding falls behind, corrections arrive too late to steer non-Clifford operations, the logical clock stalls, and the backlog compounds. This compounding is the backlog problem [1-3]. The condition usually stated for real-time viability is a utilization bound: the mean decode time per syndrome round must be below the round period, ρ = E[tdecode ]/Tround < 1. Real-time decoding demonstrations state their stability case in exactly these terms, certifying against the mean per-round latency [3,4].
Our claim is that for an important class of decoding systems the utilization bound is the wrong condition. It is not merely conservative or approximate. It is structurally wrong, in the sense that it cannot distinguish systems that differ by orders of magnitude in reliability. The class is that of windowed decoders with superlinearly event-dependent cost: the decoder periodically takes a batch (window) of accumulated syndrome and pays a decode cost that grows faster than linearly in the number of detection events the window contains. Matching decoders have this shape in practice, and we measure it directly in Section 5.4.
Our contributions:
1. A basin, not a threshold (Sec. 2, 5.1). For window cost exponent γ > 1, the deterministic backlog dynamics have two fixed points. The upper one, B*, is an unstable basin boundary that no mean-based analysis can see. At a single mean utilization (ρ0 = 0.6) we exhibit four decoders spanning unconditional stability to spontaneous failure.
2. Noise erodes the boundary (Sec. 5.1). The stochastic system diverges at perturbations the deterministic map survives. The deterministic reference is drift-matched: its batch costs use the same Poisson moments as the stochastic system’s expectations, so the gap is fluctuation physics rather than a Jensen mean inflation artifact. The analytic B* is therefore an unsafe provisioning line.
3. Spontaneous failure at nominal headroom (Sec. 5.2). At γ = 1.5 and ρ0 = 0.6, escape from the basin is driven by ordinary Poisson fluctuation alone. The measured MTTF is 1,344 ± 289 rounds, falling to 271 ± 33 at ρ0 = 0.7. The escape-time coefficient of variation is below one, so the failure is not memoryless, and MTTF alone under-describes it.
4. Greedy catch-up is the failure mode, and bounded windows are the fix (Sec. 5.3). With a per window overhead, the per-round cost c(W ) is minimized at small windows, and the measured stability cliff lands on the closed-form line c(W ) = Tround . The intuitive recovery policy, taking everything queued, is the divergent one.
5. The exponent of a real decoder is anisotropic (Sec. 5.4). Sparse blossom is near-linear when windows grow in length and approximately quadratic when they grow in density. At matched event count, density-packed windows cost 1.6× length-grown ones, and spatially clustered content, the blob-shaped syndrome footprint that leakage and cosmic-ray events actually produce [5,6], costs 7.6×. Bursts deliver density, and clustered density is the worst case we measured.
Methodologically, all simulations run on a verification first discrete-event engine (Sec. 4). Its runs are reproducible from content-addressed identities, its state machines carry runtime-checked invariants, and its paired comparisons are audited at the level of random draws. The underlying circuit model is cross-validated against Stim [7] mechanism for mechanism. The cross-validation caught three defects that internal verification could not (Sec. 4.2).
MODEL: WINDOWED DECODING AS A STATE DEPENDENT QUEUE
Syndrome rounds arrive deterministically, one per period T. All times are in ticks, with T = 10 throughout, read as 0.1 µs per tick against a 1 µs cycle. Round r carries wr ∼ Poisson(λ) detection events. We use λ = 1.6 as the model’s reference rate; its physical anchoring is order-of-magnitude. Our cross-validated distance-3 memory at p = 10−2 (Sec. 4.2) yields 1.59 detection events per three-round shot, which is 0.53 per round, while the distance-13 benchmark circuits of Section 5.4 carry 2.6 (p = 10−3) to 5.2 (p = 2 × 10−3) events per round on their much larger detector set (λ ∝ d2 at fixed p). Measured hardware brackets the same range: the detection probabilities reported for the Willow surface codes imply roughly 0.6 to 4.2 events per round at d = 3 to 7 [3]. The value λ = 1.6 sits inside that physical range. Because c1 is calibrated to a target utilization at whatever λ is chosen (see below), λ sets the granularity of fluctuations rather than the mean load, and burst sizes quoted in events should be read against the chosen λ. A 200-event burst, for example, is 125 round-equivalents at λ = 1.6. The decoder serves the queue in windows: when free, it removes up to W queued rounds (greedy: W = ∞) as one batch and occupies itself for
where E is the total number of detection events in the batch. The one-tick floor matches the simulated machine, and the integer boundary matters for the γ = 2 entries of Table 1. Equation (1) is the declared cost model whose exponent Section 5.4 measures on a production decoder. We calibrate c1 so that the steady-state single-round cost matches a target mean utilization: c0 + c1 E[wγ] = ρ0 T.
Table 1: Deterministic basin boundary B*(first integer backlog outside the basin) from the drift-matched map (2), λ = 1.6, T = 10, c0 = 1; “∞” = globally stable.
|
|
ρ0=0.5 |
0.6 |
0.7 |
0.75 |
0.8 |
0.9 |
|
γ = 1 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
γ = 1.15 |
658 |
148 |
44 |
25 |
15 |
6 |
|
γ = 1.25 |
58 |
23 |
11 |
8 |
6 |
3 |
|
γ = 1.5 |
9 |
6 |
4 |
3 |
3 |
2 |
|
γ = 2 |
4 |
3 |
2 |
2 |
2 |
2 |
The deterministic map. Under greedy windowing, a backlog of B rounds is served as one batch carrying E ∼ Poisson (Bλ) events, and t/T new rounds arrive during the service. The deterministic (mean-drift) reference evolves the backlog by the drift-matched map
Using the Poisson moment rather than the naive (Bλ)γ keeps the reference system at the same mean drift as the stochastic one. With w ≡ λ the reference would run at a lower effective utilization by Jensen’s inequality, and part of any stochastic-versus-deterministic gap would then be a calibration mismatch rather than fluctuation physics. The correction is a few percent in the boundary region: the integer fixed points of Table 1 move by at most one round relative to the naive map, but the deterministic critical bursts of Figure 1 move by up to 20%.
Figure 1: (a) The drift-matched backlog map, Eq. (2), at ρ0 = 0.6. For γ = 1 the single fixed point is globally attracting. For γ > 1 the map is convex, and the open circles mark the unstable boundary B∗, from which the backlog flows away in both directions (arrows); the callout marks the γ =1.5 boundary, B∗ = 6. (b) Basin depth B∗ versus mean utilization. At the same ρ0 the basin spans two orders of magnitude across exponents that identical mean-throughput measurements cannot distinguish.
For γ = 1, f is affine with a single, globally attracting fixed point whenever ρ0 < 1. This affine case is the textbook condition, and the queueing-literate reader will recognize it as valid precisely for state-independent service, which is the assumption that superlinear event-dependent cost violates. For γ > 1, f is convex and has two fixed points: a stable operating point Blo and an unstable boundary B∗. Any excursion beyond B∗, whether a burst or an unlucky run of fluctuations, diverges permanently, in a system whose mean utilization may be far below one. Table 1 shows how shallow the basin becomes as γ grows.
RELATED WORK
Windowed decoding is as old as the surface code itself. Overlapping-window decoding appears already in Dennis et al. [8], and the modern real-time literature develops it into sliding-window and parallel-window architectures: Skoric et al.’s parallel window decoding [9], Tan et al.’s scalable window scheme [10], and Bomb´?n et al.’s modular decoding [11]. Alongside these sit hardware decoders engineered for bounded latency, including LILLIPUT [12], Helios [13], and Barber et al.’s real-time collision-clustering decoder on FPGA [14]. The most complete demonstration to date is the real-time decoder of the Willow below-threshold experiment: streaming sparse blossom over ten-cycle processing blocks, with threads assigned to spacetime regions and fused asynchronously, holding a mean latency of 63 µs over 106 cycles at d = 5 against a 1.1 µs cycle [3]. Caune et al., integrate a sub microsecond FPGA decoder directly into the control loop and report the backlog problem avoided, certified by mean per-round latency [4]. On the qLDPC side, Relay-BP targets real-time belief-propagation decoding of bivariate-bicycle codes [15], now demonstrated on FPGAs [16]; an iteration bounded BP decoder caps its cost at an accuracy price, the same exchange Section 5.3 quantifies for windows. All of these architectures bound their windows by construction, historically motivated by latency and locality. Adaptive window designs grow the window when decoder confidence drops [17]; expansion triggered by dense content is state-dependent service cost by construction, and without a bound equivalent to c(W ) < T it reinstates the convex coupling of Section 2 at the moment expansion is most expensive. System-level analyses of the real-time stack identify round time and tail latency, rather than mean throughput, as the binding constraints [18]. Our single server greedy queue is the base case whose pathology explains, in dynamical-systems terms, why bounding the window is not merely convenient but stabilizing: greedy catch-up is the divergent policy (Sec. 5.3), and a bounded window with c(W ) < T removes the unstable fixed point entirely. The backlog problem itself is stated in Terhal’s review [1], and quantified by Smith et al. [2], at the utilization level. Our contribution is the structure below the utilization level.
The classical control side of the field is moving in a direction that makes this structure more binding, not less. HRL Laboratories has demonstrated a digitally controlled silicon quantum processing unit whose control electronics, including the syndrome-extraction sequencing for a distance-5 repetition code, run on a custom cryogenic CMOS controller inside the cryostat, with no real-time input from room-temperature equipment [19]. Decoding in that demonstration was a simple parity check evaluated offline. Section 6 returns to what the basin picture implies for decoders that must live within a cryogenic power budget.
On the queueing side, bistability and metastable congestion collapse in systems whose service degrades with state are classical subjects. Slotted ALOHA exhibits bistability [20], and loss networks exhibit metastability [21]; both show the two-fixed-point structure of Eq. (2), and that community will recognize the convex one-dimensional map on sight. The new content here is the QEC instantiation: the identification of the decoder’s event-dependent cost as the state coupling, the measured anisotropy of that cost in a production decoder, and the resulting provisioning requirement. The excursion spectrum that drives escapes has direct physical referents. Cosmic-ray events produce catastrophic, spatially clustered error bursts in superconducting arrays [5], and leakage accumulates into correlated syndrome content [6]. On gap-engineered devices the measured spectrum has shifted but not vanished: the Willow repetition-code experiments observe correlated bursts about once per hour, localized to roughly 30 qubits, with detection probabilities elevated three- to six-fold and decaying over about 400 µs [3]. The residue has a measured mechanism: ionizing radiation transiently raises the quasiparticle density and produces correlated phase-error bursts lasting about a millisecond, which survive gap engineering [22]. All of these deliver exactly the dense, clustered windows that Section 5.4 measures as the most expensive per event. Correlated noise enters the decoding literature as an accuracy problem, because decoders built on independent-error models mismatch the true error distribution. The measurements of Section 5.4 give it a second consequence: clustered syndrome is also the most expensive content per event, so one physical footprint degrades accuracy and stability together.