Splitting decoders for correcting hypergraph faults

• URL: http://arxiv.org/abs/2309.15354v1
• Date: Wed, 27 Sep 2023 01:49:04 GMT
• Title: Splitting decoders for correcting hypergraph faults
• Authors: Nicolas Delfosse, Adam Paetznick, Jeongwan Haah and Matthew B. Hastings
• Abstract summary: We propose two algorithms for splitting the hyperedges of a decoding hypergraph into edges. After splitting, hypergraph faults can be decoded using any surface code decoder. We empirically show that this strategy leads to a good performance for some classes of LDPC codes.
• Score: 2.389598109913754
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The surface code is one of the most popular quantum error correction codes. It comes with efficient decoders, such as the Minimum Weight Perfect Matching (MWPM) decoder and the Union-Find (UF) decoder, allowing for fast quantum error correction. For a general linear code or stabilizer code, the decoding problem is NP-hard. What makes it tractable for the surface code is the special structure of faults and checks: Each X and Z fault triggers at most two checks. As a result, faults can be interpreted as edges in a graph whose vertices are the checks, and the decoding problem can be solved using standard graph algorithms such as Edmonds' minimum-weight perfect matching algorithm. For general codes, this decoding graph is replaced by a hypergraph making the decoding problem more challenging. In this work, we propose two heuristic algorithms for splitting the hyperedges of a decoding hypergraph into edges. After splitting, hypergraph faults can be decoded using any surface code decoder. Due to the complexity of the decoding problem, we do not expect this strategy to achieve a good error correction performance for a general code. However, we empirically show that this strategy leads to a good performance for some classes of LDPC codes because they are defined by low weight checks. We apply this splitting decoder to Floquet codes for which some faults trigger up to four checks and verify numerically that this decoder achieves the maximum code distance for two instances of Floquet codes.

Related papers

• Demonstrating dynamic surface codes [138.1740645504286]
  We experimentally demonstrate three time-dynamic implementations of the surface code. First, we embed the surface code on a hexagonal lattice, reducing the necessary couplings per qubit from four to three. Second, we walk a surface code, swapping the role of data and measure qubits each round, achieving error correction with built-in removal of accumulated non-computational errors. Third, we realize the surface code using iSWAP gates instead of the traditional CNOT, extending the set of viable gates for error correction without additional overhead.
  arXiv  Detail & Related papers  (2024-12-18T21:56:50Z)
• Generalizing the matching decoder for the Chamon code [1.8416014644193066]
  We implement a matching decoder for a three-dimensional, non-CSS, low-density parity check code known as the Chamon code. We find that a generalized matching decoder that is augmented by a belief-propagation step prior to matching gives a threshold of 10.5% for depolarising noise.
  arXiv  Detail & Related papers  (2024-11-05T19:00:12Z)
• Breadth-first graph traversal union-find decoder [0.0]
  We develop variants of the union-find decoder that simplify its implementation and provide potential decoding speed advantages. We show how these methods can be adapted to decode non-topological quantum low-density-parity-check codes.
  arXiv  Detail & Related papers  (2024-07-22T18:54:45Z)
• Collective Bit Flipping-Based Decoding of Quantum LDPC Codes [0.6554326244334866]
  We improve both the error correction performance and decoding latency of variable degree-3 (dv-3) QLDPC codes under iterative decoding. Our decoding scheme is based on applying a modified version of bit flipping (BF) decoding, namely two-bit bit flipping (TBF) decoding.
  arXiv  Detail & Related papers  (2024-06-24T18:51:48Z)
• Learning Linear Block Error Correction Codes [62.25533750469467]
  We propose for the first time a unified encoder-decoder training of binary linear block codes. We also propose a novel Transformer model in which the self-attention masking is performed in a differentiable fashion for the efficient backpropagation of the code gradient.
  arXiv  Detail & Related papers  (2024-05-07T06:47:12Z)
• 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)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [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)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC) This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
  arXiv  Detail & Related papers  (2023-11-21T10:22:08Z)
• Graph Neural Networks for Channel Decoding [71.15576353630667]
  We showcase competitive decoding performance for various coding schemes, such as low-density parity-check (LDPC) and BCH codes. The idea is to let a neural network (NN) learn a generalized message passing algorithm over a given graph. We benchmark our proposed decoder against state-of-the-art in conventional channel decoding as well as against recent deep learning-based results.
  arXiv  Detail & Related papers  (2022-07-29T15:29:18Z)
• 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)
• Correcting spanning errors with a fractal code [7.6146285961466]
  We propose an efficient decoder for the Fibonacci code'; a two-dimensional classical code that mimics the fractal nature of the cubic code. We perform numerical experiments that show our decoder is robust to one-dimensional, correlated errors.
  arXiv  Detail & Related papers  (2020-02-26T19:00:06Z)

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.