Minimum weight perfect matching of fault-tolerant topological quantum error correction in average $O(1)$ parallel time

Abstract

Consider a 2-D square array of qubits of extent $L\times L$. We provide a proof that the minimum weight perfect matching problem associated with running a particular class of topological quantum error correction codes on this array can be exactly solved with a 2-D square array of classical computing devices, each of which is nominally associated with a fixed number $N$ of qubits, in constant average time per round of error detection independent of $L$ provided physical error rates are below fixed nonzero values, and other physically reasonable assumptions. This proof is applicable to the fully fault-tolerant case only, not the case of perfect stabilizer measurements.

8 pages, 4 figures, version accepted for publication

Cited by in corpus (8)

• Decoding algorithms for surface codes
• A scalable and fast artificial neural network syndrome decoder for surface codes
• Coherent errors and readout errors in the surface code
• Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code
• Decoding Holographic Codes with an Integer Optimisation Decoder
• Data-driven decoding of quantum error correcting codes using graph neural networks
• Realistic simulation of quantum computation using unitary and measurement channels
• Spanning Tree Matching Decoder for Quantum Surface Codes