Parallel window decoding enables scalable fault tolerant quantum computation

Quantum Error Correction (QEC) continuously generates a stream of syndrome data that contains information about the errors in the system. Decoders must process this syndrome data at the rate it is received, otherwise a data backlog problem [Terhal 2015] is encountered and the quantum computer runs exponentially slower. The leading fault-tolerant approaches to quantum computation are not scalable since decoders typically run slower as the code distance is increased. Inevitably, they reach a maximum code distance where the backlog problem and exponential slowdown arise. Superconducting quantum computers can perform QEC rounds in sub-1us time, and so this fundamental problem is also a serious practical concern and an enormous engineering challenge. Here, we present a methodology that parallelizes most decoders and achieves almost arbitrary syndrome processing speed, removing this roadblock to scalability. Our parallelization requires some classical feedback decisions to be delayed, leading to a slow-down of the logical clock speed. However, the slow-down is now polynomial in code size and so an exponential slowdown is averted. We demonstrate our parallelization speed-up using a software implementation, combining it with both union-find and minimum weight perfect matching. Furthermore, we show that parallel window decoding imposes no noticeable reduction in logical fidelity compared to an un-windowed decoder. Finally, we discuss how the same methodology can be implemented in online hardware decoders.