Parallel window decoding enables scalable fault tolerant quantum computation

Abstract

Large-scale quantum computers have the potential to hold computational capabilities beyond conventional computers for certain problems. However, the physical qubits within a quantum computer are prone to noise and decoherence, which must be corrected in order to perform reliable, fault-tolerant quantum computations. Quantum Error Correction (QEC) provides the path for realizing such computations. QEC continuously generates a continuous stream of data that decoders must process at the rate it is received, which can be as fast as 1 MHz in superconducting quantum computers. A little known fact of QEC is that if the decoder infrastructure cannot keep up, a data backlog problem is encountered and the quantum computer runs exponentially slower. Today's leading approaches to quantum error correction are not scalable as existing decoders typically run slower as the problem size is increased, inevitably hitting the backlog problem. That is: the current leading proposal for fault-tolerant quantum computation is not scalable. Here, we show how to parallelize decoding to achieve almost arbitrary speed, removing this roadblock to scalability. Our parallelization requires some classical feed forward decisions to be delayed, leading to a slow-down of the logical clock speed. However, the slow-down is now only polynomial in code size, averting the exponential slowdown. We numerically demonstrate our parallel decoder for the surface code, showing no noticeable reduction in logical fidelity compared to previous decoders and demonstrating the parallelization speedup.

arXiv comment12 pages, 7 figures

References in corpus (32)

• Topological quantum memory
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Error Correction for Quantum Memories
• Suppressing quantum errors by scaling a surface code logical qubit
• Surface code quantum computing by lattice surgery
• High threshold universal quantum computation on the surface code
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Stim: a fast stabilizer circuit simulator
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Building a fault-tolerant quantum computer using concatenated cat codes
• Quantum computing enhanced computational catalysis
• Degenerate Quantum LDPC Codes With Good Finite Length Performance
• Almost-linear time decoding algorithm for topological codes
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Windowed Decoding of Protograph-based LDPC Convolutional Codes over Erasure Channels
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Decoding Across the Quantum LDPC Code Landscape
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Effective fault-tolerant quantum computation with slow measurements
• Constant overhead quantum fault-tolerance with quantum expander codes
• Fault-tolerant error correction with the gauge color code
• Tensor-Network Simulations of the Surface Code under Realistic Noise
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Efficient Decoders for Qudit Topological Codes
• Early fault-tolerant simulations of the Hubbard model
• Single-shot error correction of three-dimensional homological product codes
• Scalable Neural Decoder for Topological Surface Codes
• Fault-Tolerant Quantum Computing in the Pauli or Clifford Frame with Slow Error Diagnostics
• Improved single-shot decoding of higher dimensional hypergraph product codes
• A circuit-level protocol and analysis for twist-based lattice surgery
• Techniques for combining fast local decoders with global decoders under circuit-level noise
• Pipelined correlated minimum weight perfect matching of the surface code

Cited by in corpus (37)

• Quantum error correction below the surface code threshold
• Sparse Blossom: correcting a million errors per core second with minimum-weight matching
• Learning to Decode the Surface Code with a Recurrent, Transformer-Based Neural Network
• Real-Time Decoding for Fault-Tolerant Quantum Computing: Progress, Challenges and Outlook
• Decoding algorithms for surface codes
• Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation
• Artificial Intelligence for Quantum Computing
• A real-time, scalable, fast and highly resource efficient decoder for a quantum computer
• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
• FPGA-based Distributed Union-Find Decoder for Surface Codes
• Localized statistics decoding for quantum low-density parity-check codes
• Error correction of transversal CNOT gates for scalable surface code computation
• Actis: A Strictly Local Union-Find Decoder
• Artificial Neural Network Syndrome Decoding on IBM Quantum Processors
• Mitigating errors in logical qubits
• XYZ ruby code: Making a case for a three-colored graphical calculus for quantum error correction in spacetime
• Local Clustering Decoder as a fast and adaptive hardware decoder for the surface code
• Union-find quantum decoding without union-find
• Spanning Tree Matching Decoder for Quantum Surface Codes
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Spatially parallel decoding for multi-qubit lattice surgery
• Degenerate quantum erasure decoding
• Single-shot and measurement-based quantum error correction via fault complexes
• High-threshold, low-overhead and single-shot decodable fault-tolerant quantum memory
• Decoding across transversal Clifford gates in the surface code
• Non-local resources for error correction in quantum LDPC codes
• Almost Linear Decoder for Optimal Geometrically Local Quantum Codes
• QUITS: A modular Qldpc code circUIT Simulator
• Bayesian mitigation of measurement errors in multiqubit experiments
• Universal quantum computation via scalable measurement-free error correction
• On the interpretability of neural network decoders
• Managing Classical Processing Requirements for Quantum Error Correction
• Decoder Dependence in Surface-Code Threshold Estimation under Digitized Hybrid Continuous-Variable and Discrete Noise
• Benchmarking fault-tolerant quantum computing hardware via QLOPS
• Streaming Belief Propagation on Mixed-Alphabet Tanner Graphs for Practical Quantum Memory
• Pinball: A Cryogenic Predecoder for Surface Code Decoding Under Circuit-Level Noise
• Snowflake: A Distributed Streaming Decoder