Sparse Blossom: correcting a million errors per core second with minimum-weight matching

Abstract

In this work, we introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder, the most widely used decoder for several important families of quantum error correcting codes, including surface codes. Our algorithm, which we call sparse blossom, is a variant of the blossom algorithm which directly solves the decoding problem relevant to quantum error correction. Sparse blossom avoids the need for all-to-all Dijkstra searches, common amongst MWPM decoder implementations. For 0.1% circuit-level depolarising noise, sparse blossom processes syndrome data in both $X$ and $Z$ bases of distance-17 surface code circuits in less than one microsecond per round of syndrome extraction on a single core, which matches the rate at which syndrome data is generated by superconducting quantum computers. Our implementation is open-source, and has been released in version 2 of the PyMatching library.

arXiv comment37 pages, 16 figures

References in corpus (24)

• Topological quantum memory
• Quantum Error Correction for Quantum Memories
• Suppressing quantum errors by scaling a surface code logical qubit
• Topological Quantum Distillation
• Operator Quantum Error Correcting Subsystems for Self-Correcting Quantum Memories
• Stim: a fast stabilizer circuit simulator
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Towards practical classical processing for the surface code
• A Neural Decoder for Topological Codes
• Dynamically Generated Logical Qubits
• Constructions and Noise Threshold of Hyperbolic Surface Codes
• Matching and maximum likelihood decoding of a multi-round subsystem quantum error correction experiment
• Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel
• A Fault-Tolerant Honeycomb Memory
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes
• Relaxing Hardware Requirements for Surface Code Circuits using Time-dynamics
• Parallel window decoding enables scalable fault tolerant quantum computation
• Fault-Tolerant Weighted Union-Find Decoding on the Toric Code
• Constructions and Noise Threshold of Topological Subsystem Codes
• Towards practical classical processing for the surface code: timing analysis
• Subsystem codes with high thresholds by gauge fixing and reduced qubit overhead
• Optimization of the surface code design for Majorana-based qubits
• Efficient color code decoders in $d\ge 2$ dimensions from toric code decoders
• Conservation laws and quantum error correction: towards a generalised matching decoder

Cited by in corpus (54)

• Quantum Error Correction resilient against Atom Loss
• Error correction of transversal CNOT gates for scalable surface code computation
• Optimizing quantum error correction protocols with erasure qubits
• Comparative study of quantum error correction strategies for the heavy-hexagonal lattice
• Fault-tolerant hyperbolic Floquet quantum error correcting codes
• Designing fault-tolerant circuits using detector error models
• Dynamical Logical Qubits in the Bacon-Shor Code
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Surface Code with Imperfect Erasure Checks
• Quantum error correction for long chains of trapped ions
• Snakes and Ladders: Adapting the surface code to defects
• Low-overhead non-Clifford fault-tolerant circuits for all non-chiral abelian topological phases
• Effectiveness of the syndrome extraction circuit with flag qubits on IBM quantum hardware
• Stabilizing Non-Abelian Topological Order against Heralded Noise via Local Lindbladian Dynamics
• Thresholds for post-selected quantum error correction from statistical mechanics
• Decoding across transversal Clifford gates in the surface code
• Lattice surgery-based logical state teleportation via noisy links
• Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
• Low-depth quantum error correction via three-qubit gates in Rydberg atom arrays
• Quantum low-density parity-check codes for erasure-biased atomic quantum processors
• End-to-end switchless architecture for fault-tolerant photonic quantum computing
• Tailoring Dynamical Codes for Biased Noise: The X${}^3$Z${}^3$ Floquet Code
• Minimising surface-code failures using a color-code decoder
• Feasibility of Logical Bell State Generation in Memory Assisted Quantum Networks
• Generalizing the matching decoder for the Chamon code
• Transversal CNOT gate with multi-cycle error correction
• Distributed Realization of Color Codes for Quantum Error Correction
• Optimal number of stabilizer measurement rounds in an idling surface code patch
• Entanglement boosting: Low-volume logical Bell pair preparation for distributed fault-tolerant quantum computation
• Lattice Surgery Compilation Beyond the Surface Code
• QUITS: A modular Qldpc code circUIT Simulator
• Multiqubit Rydberg Gates for Quantum Error Correction
• Locating Rydberg Decay Error in SWAP-Leakage Reduction Circuit Protocol
• Taming Rydberg Decay with Measurement-based Quantum Computation
• Union-Intersection Union-Find for Decoding Depolarizing Errors in Topological Codes
• Architectural Approaches to Fault-Tolerant Distributed Quantum Computing and Their Entanglement Overheads
• Soft information decoding with superconducting qubits
• Decoder Dependence in Surface-Code Threshold Estimation under Digitized Hybrid Continuous-Variable and Discrete Noise
• Pinball: A Cryogenic Predecoder for Surface Code Decoding Under Circuit-Level Noise
• Dense packing of the surface code: code deformation procedures and hook-error-avoiding gate scheduling
• Neural Decoders for Universal Quantum Algorithms
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms
• A dynamic circuit for the honeycomb Floquet code
• Symmetry in Multi-Qubit Correlated Noise Errors Enhances Surface Code Thresholds
• Planar fault-tolerant circuits for non-Clifford gates on the 2D color code
• Network Requirements for Distributed Quantum Computation
• Feedforward suppression of readout-induced faults in quantum error correction
• Increasing the distance of topological codes with time vortex defects
• Routing-based technique for defect mitigation in quantum error correction
• Overflow-Safe Polylog-Time Parallel Minimum-Weight Perfect Matching Decoder: Toward Experimental Demonstration
• Streaming Belief Propagation on Mixed-Alphabet Tanner Graphs for Practical Quantum Memory
• Snowflake: A Distributed Streaming Decoder
• Building a fusion-based quantum computer using teleported gates
• Fault-tolerant Quantum Error Correction Using a Linear Array of Emitters