Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2501.13923 · IEEE International Symposium on Information Theory (ISIT)

Efficient Mitigation of Error Floors in Quantum Error Correction Using Non-Binary Low-Density Parity-Check Codes

Kenta Kasai

Published Jun 22, 2025• 6 citations
arXivHTMLPDF

Abstract

In this paper, we propose an efficient method to reduce error floors in quantum error correction using non-binary low-density parity-check (LDPC) codes. We identify and classify cycle structures in the parity-check matrix where estimated noise becomes trapped, and develop tailored decoding methods for each cycle type. For Type-I cycles, we propose a method to make the difference between estimated and true noise degenerate. Type-II cycles are shown to be un-correctable, while for Type-III cycles, we utilize the fact that cycles in non-binary LDPC codes do not necessarily correspond to codewords, allowing us to estimate the true noise. Our method significantly improves decoding performance and reduces error floors.

DOI
10.1109/isit63088.2025.11195217

Related papers

Trapping Sets of Iterative Decoders for Quantum and Classical Low-Density Parity-Check Codes

Nithin Raveendran

Protecting logical information in the form of a classical bit or a quantum bit (qubit) is an essential step in ensuring fault-tolerant classical or quantum computation. Error correction codes and their decoders perform this step by adding redundant information that aids the decoder to recover or protect the logical information even in the presence of noise. Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems. Similarly, their quantum analogues, quantum LDPC codes are being actively pursued as excellent prospects for error correction in future fault-tolerant quantum systems due to their asymptotically non-zero rates, sparse parity check matrices, and efficient iterative decoding algorithms. This dissertation deals with failure configurations, known as \emph{trapping sets} of classical and quantum LDPC codes when decoded with iterative message passing decoding algorithms, and the \emph{error floor phenomenon} - the degradation of logical error rate performance at low physical noise regime. The study of quantum trapping sets will enable the construction of better quantum LDPC codes and also help in modifying iterative quantum decoders to achieve higher fault-tolerant thresholds and lower error floors. Towards this goal, the dissertation also presents iterative decoders for classical and quantum LDPC codes using the \emph{deep neural network framework}, novel iterative decoding algorithms, and a decoder-aware \emph{expansion-contraction method} for error floor estimation. In this dissertation, we first establish a systematic methodology by which one can identify and classify \emph{quantum trapping sets} (QTSs) according to their topological structure and decoder used. For this purpose, we leverage the known harmful configurations in the Tanner graph, called \emph{trapping sets} (TSs), from the classical error correction world. The conventional definition of a trapping set of classical LDPC codes is generalized to address the syndrome decoding scenario for quantum LDPC codes. Furthermore, we show that the knowledge of QTSs can be used to design better quantum LDPC codes and decoders. In the context of the development of novel decoders, we extend the stochastic resonance based decoders to quantum LDPC codes, propose iteration-varying message passing decoders with their message update rules learned by neural networks tuned for low logical error rate, and present a syndrome based generalized belief propagation algorithm for tackling convergence failure of iterative decoders due to the presence of short cycles. Our analysis of TSs of a layered decoding architecture clearly reveals the dependence of the harmfulness of TSs (classical or quantum) on the iterative decoder, and thus on the error floor estimates. We present a computationally efficient method for estimating error floors of LDPC codes over the binary symmetric channel without any prior knowledge of its trapping sets. The sub-graph expansion-contraction method is a general procedure for TS characterization, which lists all harmful error patterns up to a given weight for the LDPC code and decoder. Based on this decoder-aware trapping set characterization for LDPC codes, we propose a model-driven deep neural network (DNN) framework that unfolds the decoding iterations, to design the \emph{decoder diversity of finite alphabet iterative decoders (FAIDs)}. Our decoder diversity DNN-FAID delivers excellent waterfall performance along with a low error floor.

•Jan 1, 2021•1 citation

Improved Hard-Reliability Based Majority-Logic Decoding for Non-Binary LDPC Codes

Saedong Yeo, In‐Cheol Park

This letter proposes two methods to improve the iterative hard-reliability based majority-logic decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes. The first method improves the error-correcting performance by modifying the initialization process, which is based on the fact that Gray coded modulation is used in general. In addition, a storage reduction method is proposed to make the proposed decoding hardware-friendly, which reduces the memory size considerably while sustaining the error-correcting performance achieved by the modified initialization. For an NB-LDPC code over Galois field of 32 elements, the memory size is reduced by about 75% compared with that of the conventional decoding algorithm.

IEEE Communications Letters•Nov 1, 2016•16 citations

Quantum Error Correction with Girth-16 Non-Binary LDPC Codes via Affine Permutation Construction

Kenta Kasai

We propose a method for constructing quantum error-correcting codes using non-binary low-density parity-check codes whose Tanner graphs have girth 16. While conventional constructions based on circulant permutation matrices are limited to a maximum girth of 12, our approach leverages affine permutation matrices combined with a randomized sequential selection strategy to eliminate short cycles and achieve girth 16. Numerical experiments show that the proposed codes significantly reduce the number of low-weight codewords. Joint belief propagation decoding over depolarizing channels reveals that although a slight degradation appears in the waterfall region, a substantial improvement is achieved in the error floor performance. We also evaluated the minimum distance of the proposed codes and found that they achieve a larger upper bound than conventional constructions.

arXiv:2504.17790•International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•7 citations

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE Transactions on Communications•Jun 1, 2009•34 citations

Error Rate Estimation of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels Using Cycle Enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•4 citations

Logarithmic quantization scheme for reduced hardware cost and improved error floor in non-binary LDPC decoders

Yuta Toriyama, Behzad Amiri, Lara Dolecek +1 more

Non-binary low-density parity-check (NB-LDPC) codes exhibit excellent error correction performance at the cost of high computational complexity of the decoding algorithm. A logarithmic quantization scheme is proposed to reduce the VLSI implementation cost of the Min-Max decoding algorithm, by scaling down the complexity of the check node calculations that are the prime bottleneck in NB-LDPC decoding. The proposed scheme is also shown to be robust against certain types of errors, and thus enables excellent error correction capabilities even for aggressively reduced wordlengths, relative to traditional, uniform quantization schemes that exhibit either poor waterfall region performance or high error floors for a similar number of bits. The proposed scheme is directly applicable to existing architectures with few modifications and is shown to reduce the computational complexity by up to 40%, especially for large field orders.

Globecom•Dec 1, 2014•2 citations
In this paper, we propose an efficient method to reduce error floors in quantum error correction using non-binary low-density parity-check (LDPC) codes. We identify and classify cycle structures in the parity-check matrix where estimated noise becomes trapped, and develop tailored decoding methods for each cycle type. For Type-I cycles, we propose a method to make the difference between estimated and true noise degenerate. Type-II cycles are shown to be un-correctable, while for Type-III cycles, we utilize the fact that cycles in non-binary LDPC codes do not necessarily correspond to codewords, allowing us to estimate the true noise. Our method significantly improves decoding performance and reduces error floors.
Protecting logical information in the form of a classical bit or a quantum bit (qubit) is an essential step in ensuring fault-tolerant classical or quantum computation. Error correction codes and their decoders perform this step by adding redundant information that aids the decoder to recover or protect the logical information even in the presence of noise. Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems. Similarly, their quantum analogues, quantum LDPC codes are being actively pursued as excellent prospects for error correction in future fault-tolerant quantum systems due to their asymptotically non-zero rates, sparse parity check matrices, and efficient iterative decoding algorithms. This dissertation deals with failure configurations, known as \emph{trapping sets} of classical and quantum LDPC codes when decoded with iterative message passing decoding algorithms, and the \emph{error floor phenomenon} - the degradation of logical error rate performance at low physical noise regime. The study of quantum trapping sets will enable the construction of better quantum LDPC codes and also help in modifying iterative quantum decoders to achieve higher fault-tolerant thresholds and lower error floors. Towards this goal, the dissertation also presents iterative decoders for classical and quantum LDPC codes using the \emph{deep neural network framework}, novel iterative decoding algorithms, and a decoder-aware \emph{expansion-contraction method} for error floor estimation. In this dissertation, we first establish a systematic methodology by which one can identify and classify \emph{quantum trapping sets} (QTSs) according to their topological structure and decoder used. For this purpose, we leverage the known harmful configurations in the Tanner graph, called \emph{trapping sets} (TSs), from the classical error correction world. The conventional definition of a trapping set of classical LDPC codes is generalized to address the syndrome decoding scenario for quantum LDPC codes. Furthermore, we show that the knowledge of QTSs can be used to design better quantum LDPC codes and decoders. In the context of the development of novel decoders, we extend the stochastic resonance based decoders to quantum LDPC codes, propose iteration-varying message passing decoders with their message update rules learned by neural networks tuned for low logical error rate, and present a syndrome based generalized belief propagation algorithm for tackling convergence failure of iterative decoders due to the presence of short cycles. Our analysis of TSs of a layered decoding architecture clearly reveals the dependence of the harmfulness of TSs (classical or quantum) on the iterative decoder, and thus on the error floor estimates. We present a computationally efficient method for estimating error floors of LDPC codes over the binary symmetric channel without any prior knowledge of its trapping sets. The sub-graph expansion-contraction method is a general procedure for TS characterization, which lists all harmful error patterns up to a given weight for the LDPC code and decoder. Based on this decoder-aware trapping set characterization for LDPC codes, we propose a model-driven deep neural network (DNN) framework that unfolds the decoding iterations, to design the \emph{decoder diversity of finite alphabet iterative decoders (FAIDs)}. Our decoder diversity DNN-FAID delivers excellent waterfall performance along with a low error floor.
This letter proposes two methods to improve the iterative hard-reliability based majority-logic decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes. The first method improves the error-correcting performance by modifying the initialization process, which is based on the fact that Gray coded modulation is used in general. In addition, a storage reduction method is proposed to make the proposed decoding hardware-friendly, which reduces the memory size considerably while sustaining the error-correcting performance achieved by the modified initialization. For an NB-LDPC code over Galois field of 32 elements, the memory size is reduced by about 75% compared with that of the conventional decoding algorithm.
We propose a method for constructing quantum error-correcting codes using non-binary low-density parity-check codes whose Tanner graphs have girth 16. While conventional constructions based on circulant permutation matrices are limited to a maximum girth of 12, our approach leverages affine permutation matrices combined with a randomized sequential selection strategy to eliminate short cycles and achieve girth 16. Numerical experiments show that the proposed codes significantly reduce the number of low-weight codewords. Joint belief propagation decoding over depolarizing channels reveals that although a slight degradation appears in the waterfall region, a substantial improvement is achieved in the error floor performance. We also evaluated the minimum distance of the proposed codes and found that they achieve a larger upper bound than conventional constructions.
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.
Non-binary low-density parity-check (NB-LDPC) codes exhibit excellent error correction performance at the cost of high computational complexity of the decoding algorithm. A logarithmic quantization scheme is proposed to reduce the VLSI implementation cost of the Min-Max decoding algorithm, by scaling down the complexity of the check node calculations that are the prime bottleneck in NB-LDPC decoding. The proposed scheme is also shown to be robust against certain types of errors, and thus enables excellent error correction capabilities even for aggressively reduced wordlengths, relative to traditional, uniform quantization schemes that exhibit either poor waterfall region performance or high error floors for a similar number of bits. The proposed scheme is directly applicable to existing architectures with few modifications and is shown to reduce the computational complexity by up to 40%, especially for large field orders.