Addressing Stopping Failures for Small Set Flip Decoding of Hypergraph Product Codes

• URL: http://arxiv.org/abs/2311.00877v1
• Date: Wed, 1 Nov 2023 22:08:49 GMT
• Title: Addressing Stopping Failures for Small Set Flip Decoding of Hypergraph Product Codes
• Authors: Lev Stambler, Anirudh Krishna, Michael E. Beverland
• Abstract summary: Hypergraph product codes are a promising family of constant-rate quantum LDPC codes. Small-Set-Flip ($texttSSF$) is a linear-time decoding algorithm. We propose a new decoding algorithm called the Projection-Along-a-Line ($texttPAL$) decoder to supplement $textttSSF$ after stopping failures.
• Score: 1.04049929128816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For a quantum error correcting code to be used in practice, it needs to be equipped with an efficient decoding algorithm, which identifies corrections given the observed syndrome of errors.Hypergraph product codes are a promising family of constant-rate quantum LDPC codes that have a linear-time decoding algorithm called Small-Set-Flip ($\texttt{SSF}$) (Leverrier, Tillich, Z\'emor FOCS 2015). The algorithm proceeds by iteratively applying small corrections which reduce the syndrome weight. Together, these small corrections can provably correct large errors for sufficiently large codes with sufficiently large (but constant) stabilizer weight. However, this guarantee does not hold for small codes with low stabilizer weight. In this case, $\texttt{SSF}$ can terminate with stopping failures, meaning it encounters an error for which it is unable to identify a small correction. We find that the structure of errors that cause stopping failures have a simple form for sufficiently small qubit failure rates. We propose a new decoding algorithm called the Projection-Along-a-Line ($\texttt{PAL}$) decoder to supplement $\texttt{SSF}$ after stopping failures. Using $\texttt{SSF}+\texttt{PAL}$ as a combined decoder, we find an order-of-magnitude improvement in the logical error rate.

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)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. This paper attempts to find a reduction from the decoding problem of linear codes, for which several hardness results exist. We characterize the efficiency of the reduction in terms of the parameters of the decoding and problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• The closed-branch decoder for quantum LDPC codes [0.0]
  Real-time decoding is a necessity for implementing arbitrary quantum computations on the logical level. We present a new decoder for Quantum Low Density Parity Check (QLDPC) codes, named the closed-branch decoder.
  arXiv  Detail & Related papers  (2024-02-02T16:22:32Z)
• 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)
• Splitting decoders for correcting hypergraph faults [2.389598109913754]
  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.
  arXiv  Detail & Related papers  (2023-09-27T01:49:04Z)
• Fault-Tolerant Computing with Single Qudit Encoding [49.89725935672549]
  We discuss stabilizer quantum-error correction codes implemented in a single multi-level qudit. These codes can be customized to the specific physical errors on the qudit, effectively suppressing them. We demonstrate a Fault-Tolerant implementation on molecular spin qudits, showcasing nearly exponential error suppression with only linear qudit size growth.
  arXiv  Detail & Related papers  (2023-07-20T10:51:23Z)
• Scalable Quantum Error Correction for Surface Codes using FPGA [67.74017895815125]
  A fault-tolerant quantum computer must decode and correct errors faster than they appear. We report a distributed version of the Union-Find decoder that exploits parallel computing resources for further speedup. The implementation employs a scalable architecture called Helios that organizes parallel computing resources into a hybrid tree-grid structure.
  arXiv  Detail & Related papers  (2023-01-20T04:23:00Z)
• Local Probabilistic Decoding of a Quantum Code [0.0]
  flip is an extremely simple and maximally local classical decoder. Lowest-weight uncorrectable errors for this decoder are closer to correctable errors than to other uncorrectable errors. Introducing randomness into the decoder can allow it to correct these "uncorrectable" errors with finite probability.
  arXiv  Detail & Related papers  (2022-12-14T02:44:26Z)
• SoftCorrect: Error Correction with Soft Detection for Automatic Speech Recognition [116.31926128970585]
  We propose SoftCorrect with a soft error detection mechanism to avoid the limitations of both explicit and implicit error detection. Compared with implicit error detection with CTC loss, SoftCorrect provides explicit signal about which words are incorrect. Experiments on AISHELL-1 and Aidatatang datasets show that SoftCorrect achieves 26.1% and 9.4% CER reduction respectively.
  arXiv  Detail & Related papers  (2022-12-02T09:11:32Z)
• 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.