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:2504.01728 · IEEE Transactions on Information Theory

Linear Time Iterative Decoders for Hypergraph-Product and Lifted-Product Codes

Asit Kumar Pradhan, Nithin Raveendran, Narayanan Rengaswamy, Bane V. Vasic

Published Apr 27, 2026• 7 citations
arXivHTMLPDF

Abstract

Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.

DOI
10.1109/tit.2026.3687799

Related papers

Fast Fault-Tolerant Decoders for Hypergraph Product and Lifted-Product Codes

Asit Kumar Pradhan, Nithin Raveendran, David Declercq +1 more

We design low-complexity, fault-tolerant decoders for quantum low-density parity-check (QLDPC) codes with the goal of reducing decoding latency. We target two major bottlenecks of decoding under the \emph{circuit-level} noise model: (i) post-processing via order-statistics decoding (OSD), and (ii) the large number of auxiliary variable nodes commonly introduced to represent CNOT-induced correlations during syndrome extraction. Our key observation is that propagating CNOT faults (\emph{hook errors}) create \emph{stabilizer-induced} trapping sets (TSs) that are intrinsic to hypergraph-product (HGP) and lifted-product (LP) constructions. Therefore, instead of modeling each such fault with an explicit correlation node and relying on OSD to clean up the resulting failures, we design message-passing decoders that resolve the corresponding \emph{stabilizer-induced} TSs directly. We obtain these decoders by deriving QLDPC decoders from decoders for the parent classical LDPC codes and using them collectively to correct broad families of \emph{stabilizer-induced} TSs. For CNOT faults that manifest primarily as syndrome errors, we show that their effect is equivalent to a data error together with syndrome-bit measurement errors. Consequently, given repeated measurements and a decoding graph that already includes nodes representing syndrome-bit errors, no distinct variable node is needed for each CNOT fault. Using a \emph{phenomenological} Tanner graph with nodes representing only data errors and syndrome-bit errors, simulations on LP codes show a significant improvement in logical error rate relative to BP+OSD. Moreover, the improved error correction relies on low-complexity finite-state iterative decoders, targeted for fast and low-latency FPGA implementation.

cs.ITCross-listedarXiv:2608.31040•Sep 1, 2026•3 citations

Trapping Sets of Quantum LDPC Codes

Nithin Raveendran, Bane V. Vasic

Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are attractive because their hardware complexity scales only linearly with the number of physical qubits. However, they are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. These factors significantly degrade the decoder decoding probability performance and cause so-called error floor. In this paper, we establish a systematic methodology by which one can identify and classify quantum trapping sets (QTSs) according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that the knowledge of QTSs can be used to design better QLDPC codes and decoders. Frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated for some practical finite-length QLDPC codes without requiring any post-processing.

arXiv:2012.15297•Quantum•Oct 14, 2021•76 citations

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

Trapping Set Analysis of Finite-Length Quantum LDPC Codes

Nithin Raveendran, Bane V. Vasic

Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. In this paper, we develop a systematic methodology by which quantum trapping sets (QTSs) can be defined and categorized according to their topological structure. Conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that QTS information can be used to design better QLDPC code and decoder. For certain finite-length QLDPC codes, frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated without needing any post-processing steps.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•4 citations

Learning to Decode Trapping Sets in QLDPC Codes

Asit Kumar Pradhan, Nithin Raveendran, Narayanan Rengaswamy +2 more

Quantum low-density parity-check (QLDPC) codes with asymptotically nonzero rates are promising candidates for fault-tolerant quantum computation. Belief propagation (BP) based iterative decoding algorithms, a primary choice for classical LDPC codes, perform poorly for QLDPC codes due to stabilizer-induced trapping sets, resulting in a high error floor. Several decoding algorithms, like post-processing decoders, normalized BP decoders, and neural decoders, have been proposed to increase the performance in the error-floor region. However, this improvement comes at the expense of an increase in the execution time of the decoder. This paper proposes a general framework for error correction for a class of QLDPC codes called lifted-product codes using recurrent neural networks (RNNs). The RNN is employed to learn message-passing rules that can decode quantum-trapping sets. Then the standard message-passing rules are used with the learned rules to improve the error floor. While training the RNN, the quasi-cyclic property of the lifted product codes is exploited to reduce the size of the training set and the number of parameters in the network. This reduction in the number of parameters makes these decoders amenable to hardware implementation. Simulation results show that the proposed decoder performs better than the existing decoders in the literature.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 4, 2023•5 citations

Analysis of Syndrome-Based Iterative Decoder Failure of QLDPC Codes

Kirsten D. Morris, Tefjol Pllaha, Christine A. Kelley

Iterative decoder failures of quantum low density parity check (QLDPC) codes are attributed to substructures in the code’s graph, known as trapping sets, as well as degenerate errors that can arise in quantum codes. Failure inducing sets are subsets of codeword coordinates that, when initially in error, lead to decoding failure in a trapping set. In this paper we examine the failure inducing sets of QLDPC codes under syndrome-based iterative decoding, and their connection to absorbing sets in classical LDPC codes.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 4, 2023•2 citations
Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.
We design low-complexity, fault-tolerant decoders for quantum low-density parity-check (QLDPC) codes with the goal of reducing decoding latency. We target two major bottlenecks of decoding under the \emph{circuit-level} noise model: (i) post-processing via order-statistics decoding (OSD), and (ii) the large number of auxiliary variable nodes commonly introduced to represent CNOT-induced correlations during syndrome extraction. Our key observation is that propagating CNOT faults (\emph{hook errors}) create \emph{stabilizer-induced} trapping sets (TSs) that are intrinsic to hypergraph-product (HGP) and lifted-product (LP) constructions. Therefore, instead of modeling each such fault with an explicit correlation node and relying on OSD to clean up the resulting failures, we design message-passing decoders that resolve the corresponding \emph{stabilizer-induced} TSs directly. We obtain these decoders by deriving QLDPC decoders from decoders for the parent classical LDPC codes and using them collectively to correct broad families of \emph{stabilizer-induced} TSs. For CNOT faults that manifest primarily as syndrome errors, we show that their effect is equivalent to a data error together with syndrome-bit measurement errors. Consequently, given repeated measurements and a decoding graph that already includes nodes representing syndrome-bit errors, no distinct variable node is needed for each CNOT fault. Using a \emph{phenomenological} Tanner graph with nodes representing only data errors and syndrome-bit errors, simulations on LP codes show a significant improvement in logical error rate relative to BP+OSD. Moreover, the improved error correction relies on low-complexity finite-state iterative decoders, targeted for fast and low-latency FPGA implementation.
Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are attractive because their hardware complexity scales only linearly with the number of physical qubits. However, they are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. These factors significantly degrade the decoder decoding probability performance and cause so-called error floor. In this paper, we establish a systematic methodology by which one can identify and classify quantum trapping sets (QTSs) according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that the knowledge of QTSs can be used to design better QLDPC codes and decoders. Frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated for some practical finite-length QLDPC codes without requiring any post-processing.
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.
Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. In this paper, we develop a systematic methodology by which quantum trapping sets (QTSs) can be defined and categorized according to their topological structure. Conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that QTS information can be used to design better QLDPC code and decoder. For certain finite-length QLDPC codes, frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated without needing any post-processing steps.
Quantum low-density parity-check (QLDPC) codes with asymptotically nonzero rates are promising candidates for fault-tolerant quantum computation. Belief propagation (BP) based iterative decoding algorithms, a primary choice for classical LDPC codes, perform poorly for QLDPC codes due to stabilizer-induced trapping sets, resulting in a high error floor. Several decoding algorithms, like post-processing decoders, normalized BP decoders, and neural decoders, have been proposed to increase the performance in the error-floor region. However, this improvement comes at the expense of an increase in the execution time of the decoder. This paper proposes a general framework for error correction for a class of QLDPC codes called lifted-product codes using recurrent neural networks (RNNs). The RNN is employed to learn message-passing rules that can decode quantum-trapping sets. Then the standard message-passing rules are used with the learned rules to improve the error floor. While training the RNN, the quasi-cyclic property of the lifted product codes is exploited to reduce the size of the training set and the number of parameters in the network. This reduction in the number of parameters makes these decoders amenable to hardware implementation. Simulation results show that the proposed decoder performs better than the existing decoders in the literature.
Iterative decoder failures of quantum low density parity check (QLDPC) codes are attributed to substructures in the code’s graph, known as trapping sets, as well as degenerate errors that can arise in quantum codes. Failure inducing sets are subsets of codeword coordinates that, when initially in error, lead to decoding failure in a trapping set. In this paper we examine the failure inducing sets of QLDPC codes under syndrome-based iterative decoding, and their connection to absorbing sets in classical LDPC codes.