Almost-linear time decoding algorithm for topological codes

Abstract

In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of $O(n\alpha (n))$, where $n$ is the number of physical qubits and $\alpha$ is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, $\alpha (n)\le 3$. We prove that our algorithm performs optimally for errors of weight up to $(d-1)/2$ and for loss of up to $d-1$ qubits, where $d$ is the minimum distance of the code. Numerically, we obtain a threshold of $9.9\%$ for the 2d-toric code with perfect syndrome measurements and $2.6\%$ with faulty measurements.

References in corpus (8)

• Fault-tolerant quantum computation with high threshold in two dimensions
• Resource-efficient linear optical quantum computation
• Topological Quantum Distillation
• Topological fault-tolerance in cluster state quantum computation
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Percolation, renormalization, and quantum computing with non-deterministic gates
• Improved HDRG decoders for qudit and non-Abelian quantum error correction
• Purifying Quantum States: Quantum and Classical Algorithms

Cited by in corpus (51)

• Erasure conversion for fault-tolerant quantum computing in alkaline earth Rydberg atom arrays
• Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes
• Low overhead fault-tolerant quantum error correction with the surface-GKP code
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes
• Quantum Error Correction with Metastable States of Trapped Ions Using Erasure Conversion
• Neural-Network Decoders for Quantum Error Correction using Surface Codes:A Space Exploration of the Hardware Cost-Performance Trade-Offs
• Parallel window decoding enables scalable fault tolerant quantum computation
• Erasure qubits: Overcoming the $T_1$ limit in superconducting circuits
• Quantum coding with low-depth random circuits
• Quantum Error Correction with the Semion Code
• Analysing correlated noise on the surface code using adaptive decoding algorithms
• Scalable Neural Decoder for Topological Surface Codes
• Optimizing resource efficiencies for scalable full-stack quantum computers
• Exploiting Degeneracy in Belief Propagation Decoding of Quantum Codes
• A scalable and fast artificial neural network syndrome decoder for surface codes
• Control and Coherence Time Enhancement of the 0-$\pi$ Qubit
• A local pre-decoder to reduce the bandwidth and latency of quantum error correction
• Cellular automaton decoders for topological quantum codes with noisy measurements and beyond
• Morphing quantum codes
• Techniques for combining fast local decoders with global decoders under circuit-level noise
• Efficient color code decoders in $d\ge 2$ dimensions from toric code decoders
• General tensor network decoding of 2D Pauli codes
• Neural ensemble decoding for topological quantum error-correcting codes
• Conservation laws and quantum error correction: towards a generalised matching decoder
• A four-dimensional toric code with non-Clifford transversal gates
• Pipelined correlated minimum weight perfect matching of the surface code
• Generalized Belief Propagation Algorithms for Decoding of Surface Codes
• Decoding Holographic Codes with an Integer Optimisation Decoder
• Performance enhancement of surface codes via recursive MWPM decoding
• A Pair Measurement Surface Code on Pentagons
• Timing constraints imposed by classical digital control systems on photonic implementations of measurement-based quantum computing
• A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing
• Fast erasure decoder for hypergraph product codes
• LILLIPUT: A Lightweight Low-Latency Lookup-Table Based Decoder for Near-term Quantum Error Correction
• Parity-encoding-based quantum computing with Bayesian error tracking
• Improved quantum error correction using soft information
• Concatenation Schemes for Topological Fault-tolerant Quantum Error Correction
• Alibaba Cloud Quantum Development Platform: Surface Code Simulations with Crosstalk
• Interleaving: Modular architectures for fault-tolerant photonic quantum computing
• Spanning Tree Matching Decoder for Quantum Surface Codes
• Software Tools for Decoding Quantum Low-Density Parity Check Codes
• Golden codes: quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds
• Union-Find Decoders For Homological Product Codes
• Rescaling decoder for 2D topological quantum color codes on 4.8.8 lattices
• Distance-four quantum codes with combined postselection and error correction
• Practical Quantum Computing: The value of local computation
• QECOOL: On-Line Quantum Error Correction with a Superconducting Decoder for Surface Code
• Efficient Syndrome Decoder for Heavy Hexagonal QECC via Machine Learning
• Efficient decoding of random errors for quantum expander codes