Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation
- URL: http://arxiv.org/abs/2312.10950v2
- Date: Fri, 21 Jun 2024 19:45:22 GMT
- Title: Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation
- Authors: Hanwen Yao, Waleed Abu Laban, Christian Häger, Alexandre Graell i Amat, Henry D. Pfister,
- Abstract summary: We propose a decoder for QLDPC codes based on BP guided decimation (BPGD)
BPGD significantly reduces the BP failure rate due to non-convergence.
- Score: 55.8930142490617
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum low-density parity-check (QLDPC) codes have emerged as a promising technique for quantum error correction. A variety of decoders have been proposed for QLDPC codes and many of them utilize belief propagation (BP) decoding in some fashion. However, the use of BP decoding for degenerate QLDPC codes is known to have issues with convergence. These issues are typically attributed to short cycles in the Tanner graph and code degeneracy (i.e. multiple error patterns with the same syndrome). Although various methods have been proposed to mitigate the non-convergence issue, such as BP with ordered statistics decoding (BP-OSD) and BP with stabilizer inactivation (BP-SI), achieving better performance with lower complexity remains an active area of research. In this work, we propose a decoder for QLDPC codes based on BP guided decimation (BPGD), which has been previously studied for constraint satisfaction and lossy compression problems. The decimation process is applicable to both binary and quaternary BP and it involves sequentially fixing the value of the most reliable qubits to encourage BP convergence. Despite its simplicity, We find that BPGD significantly reduces the BP failure rate due to non-convergence, achieving performance on par with BP with ordered statistics decoding and BP with stabilizer inactivation, without the need to solve systems of linear equations.
Related papers
- Informed Dynamic Scheduling for QLDPC Codes [1.7802147489386628]
We consider edge-wise informed dynamic scheduling (IDS) for QLDPC codes based on syndrome-based residual belief propagation (sRBP)
Two strategies, including edge pool design and error pre-correction, are introduced to tackle this obstacle and quantum trapping sets.
A novel sRBP equipped with a predict-and-reduce-error mechanism (PRE-sRBP) is proposed.
arXiv Detail & Related papers (2024-10-02T03:00:15Z) - Decoding Quantum LDPC Codes Using Graph Neural Networks [52.19575718707659]
We propose a novel decoding method for Quantum Low-Density Parity-Check (QLDPC) codes based on Graph Neural Networks (GNNs)
The proposed GNN-based QLDPC decoder exploits the sparse graph structure of QLDPC codes and can be implemented as a message-passing decoding algorithm.
arXiv Detail & Related papers (2024-08-09T16:47:49Z) - Quaternary Neural Belief Propagation Decoding of Quantum LDPC Codes with
Overcomplete Check Matrices [45.997444794696676]
Quantum low-density parity-check (QLDPC) codes are promising candidates for error correction in quantum computers.
One of the major challenges in implementing QLDPC codes in quantum computers is the lack of a universal decoder.
We first propose to decode QLDPC codes with a belief propagation (BP) decoder operating on overcomplete check matrices.
We extend the neural BP (NBP) decoder, which was originally studied for suboptimal binary BP decoding of QLPDC codes, to quaternary BP decoders.
arXiv Detail & Related papers (2023-08-16T08:24:06Z) - 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) - 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) - Belief Propagation Neural Networks [103.97004780313105]
We introduce belief propagation neural networks (BPNNs)
BPNNs operate on factor graphs and generalize Belief propagation (BP)
We show that BPNNs converges 1.7x faster on Ising models while providing tighter bounds.
On challenging model counting problems, BPNNs compute estimates 100's of times faster than state-of-the-art handcrafted methods.
arXiv Detail & Related papers (2020-07-01T07:39:51Z) - 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.