An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

• URL: http://arxiv.org/abs/2409.01440v1
• Date: Mon, 2 Sep 2024 19:50:57 GMT
• Title: An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise
• Authors: Antonio deMarti iOlius, Imanol Etxezarreta Martinez, Joschka Roffe, Josu Etxezarreta Martinez,
• Abstract summary: We introduce the belief propagation plus ordered Tanner forest (BP+OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes. We show that the BP+OTF decoder achieves logical error suppression within an order of magnitude of state-of-the-art inversion-based decoders.
• Score: 0.562479170374811
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fault-tolerant quantum computers must be designed in conjunction with classical co-processors that decode quantum error correction measurement information in real-time. In this work, we introduce the belief propagation plus ordered Tanner forest (BP+OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes. The OTF post-processing stage removes qubits from the decoding graph until it has a tree-like structure. Provided that the resultant loop-free OTF graph supports a subset of qubits that can generate the syndrome, BP decoding is then guaranteed to converge. To enhance performance under circuit-level noise, we introduce a technique for sparsifying detector error models. This method uses a transfer matrix to map soft information from the full detector graph to the sparsified graph, preserving critical error propagation information from the syndrome extraction circuit. Our BP+OTF implementation first applies standard BP to the full detector graph, followed by BP+OTF post-processing on the sparsified graph. Numerical simulations show that the BP+OTF decoder achieves logical error suppression within an order of magnitude of state-of-the-art inversion-based decoders while maintaining almost-linear runtime complexity across all stages.

Related papers

• Accelerating Error Correction Code Transformers [56.75773430667148]
  We introduce a novel acceleration method for transformer-based decoders. We achieve a 90% compression ratio and reduce arithmetic operation energy consumption by at least 224 times on modern hardware.
  arXiv  Detail & Related papers  (2024-10-08T11:07:55Z)
• Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
  We propose a decoder for QLDPC codes based on BP guided decimation (BPGD) BPGD significantly reduces the BP failure rate due to non-convergence.
  arXiv  Detail & Related papers  (2023-12-18T05:58:07Z)
• Graph Neural Networks for Enhanced Decoding of Quantum LDPC Codes [6.175503577352742]
  We propose a differentiable iterative decoder for quantum low-density parity-check (LDPC) codes. The proposed algorithm is composed of classical belief propagation (BP) decoding stages and intermediate graph neural network (GNN) layers.
  arXiv  Detail & Related papers  (2023-10-26T19:56:25Z)
• Check-Agnosia based Post-Processor for Message-Passing Decoding of Quantum LDPC Codes [3.4602940992970908]
  We introduce a new post-processing algorithm with a hardware-friendly orientation, providing error correction performance competitive to the state-of-the-art techniques. We show that latency values close to one microsecond can be obtained on the FPGA board, and provide evidence that much lower latency values can be obtained for ASIC implementations.
  arXiv  Detail & Related papers  (2023-10-23T14:51:22Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• A Scalable Graph Neural Network Decoder for Short Block Codes [49.25571364253986]
  We propose a novel decoding algorithm for short block codes based on an edge-weighted graph neural network (EW-GNN) The EW-GNN decoder operates on the Tanner graph with an iterative message-passing structure. We show that the EW-GNN decoder outperforms the BP and deep-learning-based BP methods in terms of the decoding error rate.
  arXiv  Detail & Related papers  (2022-11-13T17:13:12Z)
• Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages [4.340338299803562]
  Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP) BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. We show that running BP with message normalization according to a serial schedule may significantly improve the decoding performance and error-floor in computer simulation.
  arXiv  Detail & Related papers  (2021-02-14T10:29:58Z)
• Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes [4.340338299803562]
  We propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP, but the passed node-to-node messages are single-valued. Message strength normalization can naturally be applied to these single-valued messages to improve the performance.
  arXiv  Detail & Related papers  (2020-02-16T03:51:59Z)
• Pruning Neural Belief Propagation Decoders [77.237958592189]
  We introduce a method to tailor an overcomplete parity-check matrix to (neural) BP decoding using machine learning. We achieve performance within 0.27 dB and 1.5 dB of the ML performance while reducing the complexity of the decoder.
  arXiv  Detail & Related papers  (2020-01-21T12:05:46Z)

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.