The realization of large-scale, fault-tolerant quantum computers hinges on overcoming the challenge of noise inherent in physical qubits. Quantum error correction (QEC) is crucial for achieving this goal by encoding logical qubits into many physical qubits and correcting errors. The process involves generating a continuous stream of syndrome data, reflecting errors detected in the system. This data must be processed by a decoder in real-time to enable feedback mechanisms, especially for non-Clifford gates, which require decoding before corrections can be applied. The rate at which syndrome data is generated (*r_gen*) must not exceed the rate at which it's processed (*r_proc*). If *r_gen*/ *r_proc* > 1, a backlog accumulates, causing an exponential slowdown in computation, a phenomenon known as Terhal's backlog argument. This argument highlights a critical scalability problem: all known decoding methods suffer from increased processing complexity as code size increases, eventually leading to this backlog. Current leading approaches, such as the overlapping recovery method (sliding window decoding), while offering online decoding, are inherently sequential and limit scalability due to the superlinear growth of decoding time with code distance. This paper proposes a solution to this fundamental roadblock by presenting a novel parallelized window decoding technique that allows for near-arbitrary processing speed, drastically improving the scalability of fault-tolerant quantum computation.

The paper reviews existing approaches to online decoding, focusing on the limitations of the overlapping recovery method (sliding window decoding). This method processes syndrome data in sequential windows, committing corrections only to older data within each window. The sequential nature, however, limits the scalability as the decoding time per window, which typically grows superlinearly with the decoding volume, becomes a bottleneck. This ultimately imposes a hard limit on the achievable code distance, hindering the development of fault-tolerant quantum computers. The authors discuss the backlog problem, referencing Terhal's work and subsequent analyses, demonstrating that exceeding the processing rate leads to exponentially longer computation times. They highlight the crucial role of real-time decoding for non-Clifford gates, emphasizing the need for solutions that maintain both speed and accuracy. The authors also mention the existence of single-shot error correction, which utilizes only a single round of measurements, but acknowledges its limitations regarding scalability and its susceptibility to the backlog problem.

The proposed solution, parallel window decoding, addresses the scalability issue by parallelizing the decoding process. It combines windowing techniques with any inner decoder that provides an (approximately) minimum-weight solution, such as minimum-weight perfect matching (MWPM) and union-find (UF). The method divides the syndrome data into overlapping windows, with some windows being decoded concurrently. Two layers of windows are utilized. In layer A, non-overlapping windows are decoded in parallel. High-confidence corrections from the central portion of each window (commit region) are committed, while corrections in the surrounding buffer regions are tentative. The tentative corrections generate artificial defects that are passed to layer B, where fully committed windows resolve the remaining defects. This approach ensures that all error chains of length less than or equal to the code distance are fully captured within at least one window. The authors describe the process in detail for matching decoders, applicable to codes where errors trigger pairs or single defects. The process involves constructing a graph representing potential errors and defects. A matching decoder finds a correction by pairing up triggered defects. The methodology also addresses data handling and communication between parallel processes, minimizing overhead. Numerical simulations are performed using both MWPM and UF decoders for rotated planar codes under different noise models, comparing the logical error rates of parallel window decoding with global decoding (decoding the entire dataset at once) and sliding window decoding. The simulations demonstrate that the parallel approach achieves near-linear speedup with the number of parallel processes, while maintaining comparable logical error rates to global decoding.

The key findings of the paper include: 1. The introduction of a novel parallel window decoding technique that overcomes the scalability limitations imposed by Terhal's backlog argument. 2. Numerical evidence demonstrating that parallel window decoding, using both MWPM and UF as inner decoders, achieves almost linear speedup with the number of processors, averting the exponential slowdown inherent in previous online decoders. 3. The demonstration that the logical error rates of parallel window decoding are comparable to those achieved with global decoding, confirming that the parallelization does not significantly compromise the fidelity of the error correction. 4. The identification of a polynomial, rather than exponential, slowdown in logical clock speed as the price paid for parallelization, a significant improvement over the exponential slowdowns observed previously. 5. The observation, through simulations, of near-linear scaling of syndrome throughput with the number of parallel processes, validating the expected scaling behavior of the algorithm. The authors use simulations on rotated planar codes subjected to circuit-level noise to confirm the performance of the algorithm, and also show that the data communication overhead among parallel processes remains negligible compared to the window decoding time itself, even with software-based parallelization.

The results demonstrate a significant advance in the scalability of fault-tolerant quantum computation. The proposed parallel window decoding method effectively addresses the long-standing problem of data backlog in online decoders, opening the path for building larger, more complex quantum computers. The comparable logical error rates achieved with global decoding showcase the effectiveness of the approach without sacrificing fidelity. The polynomial slowdown in logical clock speed represents a manageable trade-off for achieving near-arbitrary decoding speed. The findings have direct implications for the design of practical decoders, suggesting a path towards leveraging parallel processing capabilities in hardware such as FPGAs and ASICs to achieve even higher decoding throughput. This research not only validates the theoretical framework but also presents concrete numerical evidence supporting the scalability and performance of the proposed method.

This paper presents a significant breakthrough in scalable fault-tolerant quantum computation by introducing parallel window decoding. This technique effectively mitigates the data backlog problem that has hampered the scalability of previous online decoders, achieving near-arbitrary speed by parallelizing the decoding process without significantly impacting logical fidelity. Future research directions include exploring the optimal window size and overlap for different codes and noise models, further optimizing the algorithm for hardware implementation (FPGAs and ASICs), and extending the approach to other decoding problems beyond the surface code.

While the simulations demonstrate significant improvements in decoding speed and scalability, the study primarily focuses on the surface code and specific noise models. The generalizability of the findings to other quantum codes and noise environments warrants further investigation. The analysis also assumes a simplified model of communication overhead between parallel processes, which might need more detailed modeling in practical implementations. Furthermore, the simulations were conducted using software-based parallelization, and the performance in hardware implementation (FPGAs and ASICs) might vary due to factors such as communication latency and memory bandwidth.