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:1903.07404 · Physical Review A

Modified belief propagation decoders for quantum low-density parity-check codes

Alex Rigby, Jan Corne Olivier, Peter Jarvis

Published Jul 19, 2019• 42 citations
arXivHTMLPDF

Abstract

Quantum low-density parity-check codes can be decoded using a syndrome based GF(4) belief propagation decoder (where GF denotes Galois field). However, the performance of this decoder is limited both by unavoidable 4-cycles in the code's factor graph and the degenerate nature of quantum errors. For the subclass of CSS codes, the number of 4-cycles can be reduced by breaking an error into an $X$ and $Z$ component and decoding each with an individual $\mathrm{GF}(2)$ based decoder. However, this comes at the expense of ignoring potential correlations between these two error components. We present a number of modified belief propagation decoders that address these issues. We propose a $\mathrm{GF}(2)$ based decoder for CSS codes that reintroduces error correlations by reattempting decoding with adjusted error probabilities. We also propose the use of an augmented decoder, which has previously been suggested for classical binary low-density parity-check codes. This decoder iteratively reattempts decoding on factor graphs that have a subset of their check nodes duplicated. The augmented decoder can be based on a $\mathrm{GF}(4)$ decoder for any code, a $\mathrm{GF}(2)$ decoder for CSS code, or even a supernode decoder for a dual-containing CSS code. For CSS codes, we further propose a $\mathrm{GF}(2)$ based decoder that combines the augmented decoder with error probability adjustment. We demonstrate the performance of these new decoders on a range of different codes, showing that they perform favorably compared to other decoders presented in literature.

DOI
10.1103/physreva.100.012330

Related papers

Low-loss belief propagation decoder with Tanner graph in quantum error-correction codes

Dandan Yan, Xingkui Fan, Zhen-Yu Chen +1 more

Abstract Quantum error-correction codes are immeasurable resources for quantum computing and quantum communication. However, the existing decoders are generally incapable of checking node duplication of belief propagation (BP) on quantum low-density parity check (QLDPC) codes. Based on the probability theory in the machine learning, mathematical statistics and topological structure, a GF(4) (the Galois field is abbreviated as GF) augmented model BP decoder with Tanner graph is designed. The problem of repeated check nodes can be solved by this decoder. In simulation, when the random perturbation strength p=0.0115–0.0116 and number of attempts N = 60–70, the highest decoding efficiency of the augmented model BP decoder is obtained, and the low-loss frame error rate (FER) decreases to 7.1975 ×10−5. Hence, we design a novel augmented model decoder to compare the relationship between GF(2) and GF(4) for quantum code [[450,200]] on the depolarization channel. It can be verified that the proposed decoder provides the widely application range, and the decoding performance is better in QLDPC codes.

Chinese Physics B•Jul 7, 2021•9 citations

Augmented decoders for LDPC codes

Alex Rigby, JC Olivier, Hermanus Carel Myburgh +2 more

The performance of a belief propagation decoder for low-density parity-check codes is limited by the presence of trapping sets in the code’s graph. This leads to an error floor at higher signal-to-noise ratios. We propose the use of an augmented decoder which operates by iteratively decoding on a set of graphs which have a subset of repeated check nodes. We compare the augmented decoder to other modified belief propagation decoders that have been presented in the literature. We show that for all the codes considered, the augmented decoder yields the best frame error rate in the error floor region.

EURASIP Journal on Wireless Communications and Networking•Aug 2, 2018•4 citations

Quantum CSS LDPC Codes based on Dyadic Matrices for Belief Propagation-based Decoding

Alessio Baldelli, Massimo Battaglioni, Jonathan Mandelbaum +2 more

Quantum low-density parity-check (QLDPC) codes provide a practical balance between error-correction capability and implementation complexity in quantum error correction (QEC). In this paper, we propose an algebraic construction based on dyadic matrices for designing both classical and quantum LDPC codes. The method first generates classical binary quasi-dyadic LDPC codes whose Tanner graphs have girth 6. It is then extended to the Calderbank-Shor-Steane (CSS) framework, where the two component parity-check matrices are built to satisfy the compatibility condition required by the recently introduced CAMEL-ensemble quaternary belief propagation decoder. This compatibility condition ensures that all unavoidable cycles of length 4 are assembled in a single variable node, allowing the mitigation of their detrimental effects by decimating that variable node.

cs.ITCross-listedarXiv:2601.08636•IEEE International Symposium on Information Theory (ISIT)•Jan 14, 2026•0 citations

Auxiliary Nodes for BP Decoding of Quantum LDPC Codes

Daniel Tandler, Paul Bezner, Stephan ten Brink

Many recently proposed Calderbank-Shor-Steane (CSS) quantum low-density parity-check (QLDPC) codes have sparse decoding graphs, enabling syndrome-based belief propagation (BP) decoding at low complexity. Their construction, however, often results in properties that impair BP performance, such as short cycles and degeneracy. In this work, we propose a general framework for introducing auxiliary variable nodes (AVNs) and auxiliary check nodes (ACNs) into the decoding graph of CSS codes, compatible with the standard stabilizer measurement framework. This provides an additional degree of freedom in the design of the decoding graph itself and can be used to tackle the aforementioned shortcomings. We show that recently proposed techniques, 4-cycle removal and subcode ensemble decoding, can be interpreted as instances of this framework. For 4-cycle removal, we find that the gains depend strongly on the BP iteration count and check-node message scaling. Building on this framework, we further propose a graph-derived subcode ensemble decoder and demonstrate under circuit-level noise that it substantially reduces the per-round logical error rate compared with BP on the corresponding 4-cycle-free decoding graph.

arXiv:2607.12187•Jul 13, 2026•0 citations

Syndrome-Generalized Belief Propagation Decoding for Quantum Memories

Nithin Raveendran, Mohsen Bahrami, Bane V. Vasic

Quantum low-density parity check (QLDPC) codes are promising in realization of scalable, fault tolerant quantum memory for computation. Many of the QLDPC codes constructions suffer from unavoidable short cycles in their Tanner graph which degrade the decoding performance of the belief propagation (BP) algorithm. In this paper, we propose a syndrome based generalized belief propagation (GBP) algorithm for decoding of quantum LDPC codes and analyze how the proposed algorithm escapes from short cycle trapping sets effectively compared to the BP algorithm. Simulation results show improved decoding performance of the GBP algorithm over BP for the dual containing Calderbank, Shor and Steane (CSS) codes when cycles of length 4 are considered in the region based approach.

International Conference on Communications•May 1, 2019•10 citations

Augmented Belief-Propagation Decoding of Low-Density Parity-Check Codes

Nedeljko Varnica, M.P.C. Fossorier, A. Kavcic

We propose an augmented belief-propagation (BP) decoder for low-density parity-check (LDPC) codes which can be used on memoryless or intersymbol-interference (ISI) channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol-selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared with the standard locally operating BP decoder) for short LDPC codes decoded on both memoryless and ISI Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.

IEEE Transactions on Communications•Oct 1, 2006•6 citations
Quantum low-density parity-check codes can be decoded using a syndrome based GF(4) belief propagation decoder (where GF denotes Galois field). However, the performance of this decoder is limited both by unavoidable 4-cycles in the code's factor graph and the degenerate nature of quantum errors. For the subclass of CSS codes, the number of 4-cycles can be reduced by breaking an error into an XXX and ZZZ component and decoding each with an individual GF(2)\mathrm{GF}(2)GF(2) based decoder. However, this comes at the expense of ignoring potential correlations between these two error components. We present a number of modified belief propagation decoders that address these issues. We propose a GF(2)\mathrm{GF}(2)GF(2) based decoder for CSS codes that reintroduces error correlations by reattempting decoding with adjusted error probabilities. We also propose the use of an augmented decoder, which has previously been suggested for classical binary low-density parity-check codes. This decoder iteratively reattempts decoding on factor graphs that have a subset of their check nodes duplicated. The augmented decoder can be based on a GF(4)\mathrm{GF}(4)GF(4) decoder for any code, a GF(2)\mathrm{GF}(2)GF(2) decoder for CSS code, or even a supernode decoder for a dual-containing CSS code. For CSS codes, we further propose a GF(2)\mathrm{GF}(2)GF(2) based decoder that combines the augmented decoder with error probability adjustment. We demonstrate the performance of these new decoders on a range of different codes, showing that they perform favorably compared to other decoders presented in literature.
Abstract Quantum error-correction codes are immeasurable resources for quantum computing and quantum communication. However, the existing decoders are generally incapable of checking node duplication of belief propagation (BP) on quantum low-density parity check (QLDPC) codes. Based on the probability theory in the machine learning, mathematical statistics and topological structure, a GF(4) (the Galois field is abbreviated as GF) augmented model BP decoder with Tanner graph is designed. The problem of repeated check nodes can be solved by this decoder. In simulation, when the random perturbation strength p=0.0115–0.0116 and number of attempts N = 60–70, the highest decoding efficiency of the augmented model BP decoder is obtained, and the low-loss frame error rate (FER) decreases to 7.1975 ×10−5. Hence, we design a novel augmented model decoder to compare the relationship between GF(2) and GF(4) for quantum code [[450,200]] on the depolarization channel. It can be verified that the proposed decoder provides the widely application range, and the decoding performance is better in QLDPC codes.
The performance of a belief propagation decoder for low-density parity-check codes is limited by the presence of trapping sets in the code’s graph. This leads to an error floor at higher signal-to-noise ratios. We propose the use of an augmented decoder which operates by iteratively decoding on a set of graphs which have a subset of repeated check nodes. We compare the augmented decoder to other modified belief propagation decoders that have been presented in the literature. We show that for all the codes considered, the augmented decoder yields the best frame error rate in the error floor region.
Quantum low-density parity-check (QLDPC) codes provide a practical balance between error-correction capability and implementation complexity in quantum error correction (QEC). In this paper, we propose an algebraic construction based on dyadic matrices for designing both classical and quantum LDPC codes. The method first generates classical binary quasi-dyadic LDPC codes whose Tanner graphs have girth 6. It is then extended to the Calderbank-Shor-Steane (CSS) framework, where the two component parity-check matrices are built to satisfy the compatibility condition required by the recently introduced CAMEL-ensemble quaternary belief propagation decoder. This compatibility condition ensures that all unavoidable cycles of length 4 are assembled in a single variable node, allowing the mitigation of their detrimental effects by decimating that variable node.
Many recently proposed Calderbank-Shor-Steane (CSS) quantum low-density parity-check (QLDPC) codes have sparse decoding graphs, enabling syndrome-based belief propagation (BP) decoding at low complexity. Their construction, however, often results in properties that impair BP performance, such as short cycles and degeneracy. In this work, we propose a general framework for introducing auxiliary variable nodes (AVNs) and auxiliary check nodes (ACNs) into the decoding graph of CSS codes, compatible with the standard stabilizer measurement framework. This provides an additional degree of freedom in the design of the decoding graph itself and can be used to tackle the aforementioned shortcomings. We show that recently proposed techniques, 4-cycle removal and subcode ensemble decoding, can be interpreted as instances of this framework. For 4-cycle removal, we find that the gains depend strongly on the BP iteration count and check-node message scaling. Building on this framework, we further propose a graph-derived subcode ensemble decoder and demonstrate under circuit-level noise that it substantially reduces the per-round logical error rate compared with BP on the corresponding 4-cycle-free decoding graph.
Quantum low-density parity check (QLDPC) codes are promising in realization of scalable, fault tolerant quantum memory for computation. Many of the QLDPC codes constructions suffer from unavoidable short cycles in their Tanner graph which degrade the decoding performance of the belief propagation (BP) algorithm. In this paper, we propose a syndrome based generalized belief propagation (GBP) algorithm for decoding of quantum LDPC codes and analyze how the proposed algorithm escapes from short cycle trapping sets effectively compared to the BP algorithm. Simulation results show improved decoding performance of the GBP algorithm over BP for the dual containing Calderbank, Shor and Steane (CSS) codes when cycles of length 4 are considered in the region based approach.
We propose an augmented belief-propagation (BP) decoder for low-density parity-check (LDPC) codes which can be used on memoryless or intersymbol-interference (ISI) channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol-selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared with the standard locally operating BP decoder) for short LDPC codes decoded on both memoryless and ISI Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.