Parallel window decoding enables scalable fault tolerant quantum computation

The paper addresses the challenge of real-time (online) decoding for fault-tolerant quantum computation, where certain non-Clifford operations (e.g., T gates via gate teleportation) require rapid, reliable classical feed-forward based on decoded syndrome data. Existing decoders slow with system size, leading to a backlog where the syndrome generation rate exceeds processing rate, causing exponential slowdowns (Terhal’s backlog argument). The authors aim to develop a decoding framework that scales with hardware size, avoids the backlog, and maintains logical fidelity comparable to global decoding, while acknowledging finite classical latency.

The authors build on prior concepts: Terhal’s backlog argument establishing exponential slowdowns when processing lags generation; the overlapping recovery method of Dennis et al., later known as sliding window decoding in classical LDPC contexts, which commits older corrections while deferring recent ones but remains inherently sequential; and single-shot error correction approaches in higher-dimensional topological codes and qLDPC codes, which still face backlog if decoding exceeds round time and currently lack surface-code-level thresholds. They note contemporaneous similar results by Alibaba teams reporting logical fidelities but without decoding speed numerics.

They propose parallelized window decoding that wraps around an inner decoder assumed to return (approximately) minimum-weight corrections (e.g., minimum-weight perfect matching, MWPM; or union-find, UF). The syndrome history is partitioned into overlapping windows. Layer A comprises many non-overlapping windows decoded in parallel; each window has a commit region in its middle (n_com rounds) where high-confidence corrections are committed and buffer regions (n_buf rounds) at the edges whose tentative corrections are not committed but instead converted into artificial defects passed forward. Layer B windows span the gaps between adjacent Layer A commit regions and are decoded to fully resolve remaining defects, now with smooth time boundaries (no buffers) because nearby defects were already addressed. This construction ensures that any error chain of length up to the code distance d is captured within some window, preserving fidelity comparable to global decoding. They implement the approach for the 3D decoding graph of the rotated planar (surface) code under circuit-level noise, using MWPM and UF as inner decoders. Data pipelining allows dispatching each Layer A window to a worker as soon as its last round is measured; a Layer B window begins once its two adjacent Layer A windows finish and supply artificial defects. Communication is minimal: each worker receives defect data and returns artificial defects and the logical effect of committed corrections. The throughput condition to avoid backlog, assuming negligible overhead, is N_par (n_com + n_w) T_rd ≥ 2 t_w, where N_par is the number of parallel processes, T_rd is time per QEC round, n_w is window length, and t_w is the time to decode a window. Thus, N_par ≥ 2 t_w / ((n_com + n_w) T_rd). They evaluate performance via numerical simulations (Python implementations) and compare parallel window decoding to sliding and global decoding across code distances, numbers of rounds, and noise models.

• Parallel window decoding achieves logical error rates indistinguishable (within numerical error bars) from global MWPM decoding for rotated planar surface codes under circuit-level noise across a range of code distances and numbers of rounds; similar results hold for UF-based decoders and other noise models.
• The approach removes the exponential slowdown of Terhal’s backlog by enabling almost arbitrary processing throughput through parallelism; remaining latency introduces only a linear slow-down of the logical clock proportional to the window decoding time t_w.
• Near-linear scaling of decoding throughput with the number of parallel processes is demonstrated: using N_par = 8 yields nearly an 8× increase in decoding speed, with minor sub-linearity due to software overheads (more noticeable with UF due to faster per-window decoding).
• Communication overhead is low because only defect data and artificial defects/logical effects are exchanged; hardware implementations (FPGA/ASIC) are well-suited to exploit high degrees of parallelism.
• Backlog avoidance condition derived: N_par ≥ 2 t_w / ((n_com + n_w) T_rd).

The proposed parallel window framework directly addresses the decoding backlog by distributing workload across many parallel processes while maintaining high-fidelity corrections comparable to global decoding. By committing only high-confidence corrections in the center of each window and deferring boundary regions via artificial defects, the scheme reconciles overlapping windows without sacrificing performance. This enables scalable fault-tolerant computation: as problem sizes grow, adding polynomially many classical processors sustains required throughput, converting an exponential slowdown into a manageable linear latency increase tied to window solve time. The method is decoder-agnostic (applicable to MWPM, UF, and other approximate minimum-weight decoders), requires limited communication, and maps naturally to hardware accelerators. The results set practical requirements for classical decoding infrastructure and suggest architectures for pipelined, online decoders supporting timely feed-forward for non-Clifford gates.

The paper introduces parallel window decoding, a scalable, decoder-agnostic approach that achieves near-global-decoder logical fidelities while enabling arbitrarily high throughput via parallelism. It averts Terhal’s backlog by allowing polynomial scaling of classical resources and introduces only a linear latency in logical clock speed. Numerical experiments on surface codes (circuit-level noise) with MWPM and UF confirm both fidelity preservation and near-linear speedup (e.g., ~8× with 8 processes). Future directions include hardware implementations (FPGA/ASIC) to maximize parallelism, refined data pipelining for online operation, tuning buffer/commit parameters, and extending the framework to other codes and decoding problems.

• Residual latency remains due to per-window decoding time t_w, slowing the logical clock even though throughput scales.
• Dependencies between Layer A and Layer B windows introduce synchronization points; Layer B cannot start until adjacent Layer A windows finish.
• Near-linear speedup may degrade due to software and communication overheads, particularly for low-distance codes or very fast inner decoders (e.g., UF), though hardware accelerators can mitigate this.
• Correctness relies on appropriately chosen buffer sizes to ensure error chains up to distance d are captured; suboptimal parameters could affect fidelity.
• Results are numerical; no hardware-in-the-loop demonstrations are presented.
• Assumes availability of inner decoders that (approximately) minimize correction weight; performance may vary with decoder quality.