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

• URL: http://arxiv.org/abs/2303.15933v1
• Date: Tue, 28 Mar 2023 12:42:54 GMT
• Title: Sparse Blossom: correcting a million errors per core second with minimum-weight matching
• Authors: Oscar Higgott and Craig Gidney
• Abstract summary: We introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder. 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Minimum-Weight Parity Factor Decoder for Quantum Error Correction [3.523914647883289]
  HyperBlossom is a unified framework that formulates MLE decoding as a Minimum-Weight Parity Factor problem.<n>HyperBlossom unifies all the existing graph-based decoders like (Hypergraph) Union-Find decoders and Minimum-Weight Perfect Matching (MWPM) decoders.<n>HyperBlossom achieves a 4.8x lower logical error rate compared to the MWPM decoder on the distance-11 surface code.
  arXiv  Detail & Related papers  (2025-08-07T01:44:34Z)
• SOME: Symmetric One-Hot Matching Elector -- A Lightweight Microsecond Decoder for Quantum Error Correction [3.6525689137085178]
  We propose a novel decoder that reformulates the QEC decoding task as a Quadratic Unconstrained Binary Optimization problem.<n>It achieves up to a 99.9x reduction in variable count and reduces decoding times from milliseconds to microseconds on a single-threaded commodity CPU.<n>It also maintains performance up to a 10.5% physical error rate, surpassing the highest known threshold of MWPM@.
  arXiv  Detail & Related papers  (2025-07-31T14:57:39Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Decision-tree decoders for general quantum LDPC codes [0.9374652839580183]
  We introduce Decision Tree Decoders (DTDs), which rely only on the sparsity of the binary check matrix. DTDs construct corrections incrementally by adding faults one-by-one, forming a path through a Decision Tree (DT) We propose two explicit DTD algorithms that can be applied to any qLDPC code.
  arXiv  Detail & Related papers  (2025-02-23T02:29:14Z)
• Ambiguity Clustering: an accurate and efficient decoder for qLDPC codes [0.0]
  We introduce Ambiguity Clustering (AC), an algorithm which seeks to divide measurement data into clusters which are decoded independently. AC is between one and three orders of magnitude faster than BP-OSD with no reduction in logical fidelity. Our CPU implementation of AC is already fast enough to decode the 144-qubit Gross code in real time for neutral atom and trapped ion systems.
  arXiv  Detail & Related papers  (2024-06-20T17:39:31Z)
• Promatch: Extending the Reach of Real-Time Quantum Error Correction with Adaptive Predecoding [2.3158782497981205]
  We propose a real-time adaptive predecoder that predecodes both simple and complex patterns using a locality-aware, greedy approach. Promatch represents the first real-time decoding framework capable of decoding surface codes of distances 11 and 13. We demonstrate that running Promatch concurrently with the recently proposed Astrea-G achieves LER equivalent to MWPM LER, $3.4times10-15$, for distance 13.
  arXiv  Detail & Related papers  (2024-04-04T01:16:49Z)
• Progressive-Proximity Bit-Flipping for Decoding Surface Codes [8.971989179518214]
  Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation. Existing decoders often fall short of meeting requirements such as having low computational complexity. We propose a novel bit-flipping (BF) decoder tailored for toric and surface codes.
  arXiv  Detail & Related papers  (2024-02-24T22:38:05Z)
• Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Fast Flux-Activated Leakage Reduction for Superconducting Quantum Circuits [84.60542868688235]
  leakage out of the computational subspace arising from the multi-level structure of qubit implementations. We present a resource-efficient universal leakage reduction unit for superconducting qubits using parametric flux modulation. We demonstrate that using the leakage reduction unit in repeated weight-two stabilizer measurements reduces the total number of detected errors in a scalable fashion.
  arXiv  Detail & Related papers  (2023-09-13T16:21:32Z)
• Fusion Blossom: Fast MWPM Decoders for QEC [6.878819782873719]
  Existing implementations of the Minimum-Weight Perfect Matching decoder cannot catch up with quantum hardware. We design and implement a fast MWPM decoder, called Parity Blossom, which reaches a time complexity almost proportional to the number of defect measurements. Given a practical circuit-level noise of 0.1%, Fusion Blossom can decode a million measurement rounds per second up to a code distance of 33.
  arXiv  Detail & Related papers  (2023-05-15T02:31:06Z)
• The END: An Equivariant Neural Decoder for Quantum Error Correction [73.4384623973809]
  We introduce a data efficient neural decoder that exploits the symmetries of the problem. We propose a novel equivariant architecture that achieves state of the art accuracy compared to previous neural decoders.
  arXiv  Detail & Related papers  (2023-04-14T19:46:39Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)
• OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
  Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization. We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming. This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
  arXiv  Detail & Related papers  (2021-09-16T10:59:33Z)
• PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching [0.0]
  PyMatching is a package for decoding quantum error-correcting codes with the minimum-weight perfect matching (MWPM) algorithm. PyMatching supports the use of weighted edges, hook errors, boundaries and measurement errors, enabling fast decoding and simulation of fault-tolerant quantum computing.
  arXiv  Detail & Related papers  (2021-05-27T12:10:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.