A fault-tolerant quantum computer must continuously decode a stream of syndrome data, yet the computational work required by each decoding window is random. Although average throughput determines whether the syndrome backlog is stable (doesn’t grow without bound), it does not determine the buffer capacity needed to meet a target overflow probability. Here, we model syndrome buffering as a queue and show how its required depth depends on the tail of the decoding-work distribution. For heavy-tailed work, established queueing results imply that sliding-window decoding can require buffer depths that grow superpolynomially in the logarithm of the inverse overflow probability. Parallel-window decoding suppresses the overflow tail through concurrent service, with the suppression exponent determined by the number of spare decoders; under out-of-order release, the number of spare decoders required for a fixed buffer and target overflow probability grows logarithmically with the inverse target probability. We find evidence of heavy-tailed decoding work in Relay-BP on the gross-code and minimum-weight perfect matching on the surface code. These results identify syndrome-buffer capacity and memory-release policy as important design considerations for real-time quantum error correction.
A fault-tolerant quantum computer must continuously decode a stream of syndrome data, yet the computational work required by each decoding window is random. Although average throughput determines whether the syndrome backlog is stable (doesn’t grow without bound), it does not determine the buffer capacity needed to meet a target overflow probability. Here, we model syndrome buffering as a queue and show how its required depth depends on the tail of the decoding-work distribution. For heavy-tailed work, established queueing results imply that sliding-window decoding can require buffer depths that grow superpolynomially in the logarithm of the inverse overflow probability. Parallel-window decoding suppresses the overflow tail through concurrent service, with the suppression exponent determined by the number of spare decoders; under out-of-order release, the number of spare decoders required for a fixed buffer and target overflow probability grows logarithmically with the inverse target probability. We find evidence of heavy-tailed decoding work in Relay-BP on the gross-code and minimum-weight perfect matching on the surface code. These results identify syndrome-buffer capacity and memory-release policy as important design considerations for real-time quantum error correction.
The practical realization of fault-tolerant quantum computing relies fundamentally on the rapid and accurate decoding of quantum error-correcting codes. However, existing analyses of decoding algorithms often treat the problem as a sequence of independent, state-less optimization tasks, typically optimizing for a scalar metric such as logical error rate or average latency. In reality, the decoding process in a continuously operating quantum computer is tightly constrained by the physical rate of syndrome extraction and the finite capacity of the classical processing buffer, creating a non-trivial backlog dynamic. In this work, we present a rigorous mathematical framework that formulates the quantum decoding problem under strict backlog constraints as a discrete-time Markov Decision Process (MDP). By augmenting the state space to include both the real-time syndrome weight and the instantaneous buffer backlog, we shift the paradigm from one-dimensional thresholding to a multi-dimensional sequential control problem. We demonstrate mathematically and empirically that when the queue dynamics are explicitly modeled, the optimal policy diverges significantly from simple syndrome-weight thresholds. Furthermore, we employ Deep Q-Networks (DQN) to discover non-linear policies that inherently balance the trade-off between logical error suppression and queue stability. Our control-theoretic analysis reveals that incorporating state-space representations of the backlog allows RL agents to robustly prevent buffer overflow while maintaining near-optimal logical fidelity. Through extensive simulation on surface codes under circuit-level noise, our DQN agent strictly outperforms naive two-dimensional grid-search baselines, achieving a zero overflow rate in critical regimes where traditional thresholding fails catastrophically.
Sparse-Blossom Decoding in o(1) Time
Matching-based decoding is widely used in quantum error correction, and accelerating it is key to enabling fast and scalable fault-tolerant quantum computation. Minimum-weight perfect matching (MWPM) decoding provides rigorous guarantees for error suppression, while sparse blossom enables its practical implementation at modest problem sizes. However, the runtime of existing sparse-blossom implementations unavoidably increases with problem size, motivating a rigorous parallelization framework that guarantees correctness and a runtime shorter than the syndrome-extraction timescale. Here, we present such a framework and prove that the resulting parallel sparse-blossom algorithm produces the same correction as the original, non-parallel sparse blossom. For the rotated surface code with code distance d and physical error rates below a finite threshold, we prove that the average parallel runtime of decoding for O(d) rounds of syndrome extraction is upper bounded by a quasi-polylogarithmic function of d. For a d-round decoding window, this implies that the average parallel runtime per round is o(1). We also perform numerical simulation to identify conditions under which the parallel runtime per round decreases with increasing code distance. These results suggest that increasing code distance need not lead to longer parallel decoding times, providing a foundation for scalable parallel matching-based decoding.
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 supercon-ducting 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. These Poisson times are upper bounds: modulating the arrival rate at fixed mean load shortens them monotonically with the measured dispersion index of the arrivals, fourfold by D ≈ 3, and a dispersion excess of twelve percent already uncensors the ρ0 = 0.5 ensemble. 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. The anisotropy is a property of the matching class rather than of one implementation, since a second exact-MWPM decoder reproduces the density exponent, while a BP+OSD decoder is nearly event-independent: no basin, but orders of magnitude more cost per window. The basin is the price of event-adaptive decoding. 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 rule survives finite memory: under greedy service a queue cap acts as an implicit window, and a cap on the unstable side of the same line pins at the cap and sheds rounds indefinitely, so adding buffer memory makes the greedy policy strictly worse. The simulation model is cross-validated against Stim at the level of individual fault mechanisms.
Practical implementations of quantum error correction (QEC) require rapid measurement and continuous processing of the syndrome information in order to prevent a backlog of unprocessed data. While ``static'' QEC is theoretically well understood via mappings to equilibrium statistical mechanics models, such an understanding of ``real-time'' QEC is currently lacking. Here, we study the kinetics of sliding window decoding (SWD), an implementation of real-time decoding that acts on temporally local windows of noisy syndrome information and commits to corrections irreversibly at a nonzero rate. We propose an effective description of SWD in terms of a stochastic kinetic process, where Z2-charged point particles undergo parity-conserving reaction and diffusion. This model describes dynamics at length and time scales large compared to the window size W, whereas physics at scales smaller than W leads to nontrivial W-dependent scaling of the effective parameters. We identify the rate of decoding 1/W as a relevant perturbation to the decodable phase. We also show broad applicability of our results by changing many microscopic details of SWD without affecting the effective description.
The practical realization of fault-tolerant quantum computing relies fundamentally on the rapid and accurate decoding of quantum error-correcting codes. However, existing analyses of decoding algorithms often treat the problem as a sequence of independent, state-less optimization tasks, typically optimizing for a scalar metric such as logical error rate or average latency. In reality, the decoding process in a continuously operating quantum computer is tightly constrained by the physical rate of syndrome extraction and the finite capacity of the classical processing buffer, creating a non-trivial backlog dynamic. In this work, we present a rigorous mathematical framework that formulates the quantum decoding problem under strict backlog constraints as a discrete-time Markov Decision Process (MDP). By augmenting the state space to include both the real-time syndrome weight and the instantaneous buffer backlog, we shift the paradigm from one-dimensional thresholding to a multi-dimensional sequential control problem. We demonstrate mathematically and empirically that when the queue dynamics are explicitly modeled, the optimal policy diverges significantly from simple syndrome-weight thresholds. Furthermore, we employ Deep Q-Networks (DQN) to discover non-linear policies that inherently balance the trade-off between logical error suppression and queue stability. Our control-theoretic analysis reveals that incorporating state-space representations of the backlog allows RL agents to robustly prevent buffer overflow while maintaining near-optimal logical fidelity. Through extensive simulation on surface codes under circuit-level noise, our DQN agent strictly outperforms naive two-dimensional grid-search baselines, achieving a zero overflow rate in critical regimes where traditional thresholding fails catastrophically.
Surface codes are a popular error-correction route to fault-tolerant quantum computation. The so-called exponential backlog problem that can arise when one has to do logical T-gates within the surface code demands real-time decoding of the syndrome information to diagnose the appropriate Pauli frame in which to do the gate. This in turn puts a minimum requirement on the communication rate between the quantum processing unit, where the syndrome information is collected, and the classical processor, where the decoding algorithm is run. This minimum communication rate can be difficult to achieve while preserving the quality of the quantum processor. Here, we present two decoders that make use of a reduced syndrome information volume, relying on a number of syndrome bits that scale only as the width -- and not the usual area -- of the surface-code patch. This eases the communication requirements necessary for real-time decoding.