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:2311.18488 · International Conference on Communications

Low-Complexity Linear Programming Based Decoding of Quantum LDPC Codes

Sana Javed, Francisco García-Herrero, Bane V. Vasic, Mark F. Flanagan

Published Jun 9, 2024• 7 citations
arXivHTMLPDF

Abstract

This paper proposes two approaches for reducing the impact of the error floor phenomenon when decoding quantum low-density parity-check codes with belief propagation based algorithms. First, a low-complexity syndrome-based linear programming (SB- LP) decoding algorithm is proposed, and second, the proposed SB-LP is applied as a post-processing step after syndrome-based min-sum (SB-MS) decoding. For the latter case, a new early stopping criterion is introduced to decide when to activate the SB- LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for a sample hypergraph code, that the proposed decoder can lower the error floor by two to three orders of magnitude compared to SB-MS for the same total number of decoding iterations.

DOI
10.1109/icc51166.2024.10622622

Related papers

Low-Complexity Syndrome-Based Linear Programming Decoding of Quantum LDPC Codes

Sana Javed, Sergio Colet, Francisco García-Herrero +4 more

This paper proposes a novel low-complexity syndrome-based linear programming (SB-LP) decoding algorithm for decoding quantum low-density parity-check (LDPC) codes. Under the code-capacity model, the SB-LP decoder can be used as a standalone decoder; however, it is particularly powerful when used as a post-processing step following syndrome-based min-sum (SB-MS) decoding. In the latter case, the proposed decoder is shown to be capable of significantly reducing the error floor of the SB-MS decoder for both flooded and layered SB-MS scheduling. Also, an early stopping criterion is introduced to decide when to activate the SB-LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for some example hypergraph and generalized bicycle (GB) codes, that the proposed decoder can lower the error floor by one to three orders of magnitude compared to SB-MS for the same total number of decoding iterations. Furthermore, for the class of GB codes, it is shown that as the minimum distance of the code increases, the logical error rate provided by the proposed decoder also improves, indicating that the solution is scalable. Under the circuit-level noise model, it is shown that while the SB-LP decoder does not fully replace the need for ordered statistics decoding (OSD) when flooded SB-MS is used as a preliminary step, it reduces the number of calls to the OSD post-processor, which directly impacts the overall latency. Additionally, the method offers a syndrome-matching decoder and improves the accuracy of the logical error rate for bivariate bicycle codes of distances six to eighteen, particularly at low error rates, when compared to the BP+OSD benchmark.

IEEE Transactions on Quantum Engineering•Dec 4, 2025•0 citations

A Two-Stage Decoding Algorithm to Lower the Error-Floors for LDPC Codes

Xueting Zhang, Shaoping Chen

A two-stage decoding algorithm to lower the error-floor for low-density parity-check (LDPC) codes is presented. An efficient stopping criterion is proposed to avoid unnecessary iterations in the first stage. If the stopping criterion is reached, the first stage decoding will be terminated and the second stage decoding will be started, where the unsuccessfully decoded words are re-decoded by manipulating the log-likelihood ratio (LLR) of two types of specifically selected variable nodes. Simulation results show that the proposed algorithm can effectively lower the error floor of LDPC codes while maintaining a low decoding complexity.

IEEE Communications Letters•Feb 9, 2015•12 citations

Syndrome-Based Min-Sum vs OSD-0 Decoders: FPGA Implementation and Analysis for Quantum LDPC Codes

Javier Valls, Francisco García-Herrero, Nithin Raveendran +1 more

Quantum processors need to improve their reliability to scale up the number of qubits and increase the number of algorithms that can execute. To reduce the logical error rate of the quantum systems, the use of error correction codes and decoders has been established as a low-cost and feasible approach, with good results from a theoretical perspective, for mid and long-term architectures. While most of the authors are focused on the algorithms to improve the correction capability of quantum computers, without taking into account a fundamental implementation aspect for their deployment in a real system, i.e., their latency must be bounded to avoid the qubit decoherence, only a few propose hardware architectures and they just include time estimations of their decoding latency. However, a real implementation has not been shown yet. In this work, we analyze from the point of view of hardware implementation two algorithmic options based on quantum low-density parity-check (QLDPC) codes: a) belief propagation min-sum decoders combined with codes with good error-floor behavior and b) belief propagation min-sum decoders concatenated with ordered statistics decoders (OSDs) for codes with early error-floor. The bounds for the maximum clock frequency required by the decoders to decode within the qubit coherence time are established as a parameter to show if a practical implementation is possible with the present or near future FPGA technology. Furthermore, real implementation results for a Xilinx FPGA device are provided, showing that some solutions can meet the timing constraints set up by the state-of-the-art quantum processors.

IEEE Access•Jan 1, 2021•36 citations

Flipped and augmented decoding algorithm for low-density parity-check codes

Jianhua Lü

A two stage belief-propagation(TSBP) decoding algorithm was developed based on trapping set state(TSS) detection to reduce the error floor of low-density parity-check(LDPC) codes.The algorithm uses belief-propagation algorithm until the TSS is detected,then iterative decoding is attempted to continue through flipping and augmenting the initial values of the possible error bits until the decoding succeeds or the maximum number of attempts is reached.Simulations show that the algorithm significantly reduces the maximum number of iterations for decoding in the error floor region,and with a few additional attempts,the error floor of LDPC codes can be reduced by nearly two orders of magnitude.

Journal of Tsinghua University(Science and Technology)•Jan 1, 2008•0 citations

Syndrome Adaptive Gain Control for Min-Sum Decoding of Quantum LDPC Codes

Hernan X. Cordova, Alexios Balatsoukas‐Stimming, Yunus Can Gültekin +2 more

Min-Sum (MS) decoding is a popular low-complexity alternative to belief propagation (BP), retaining only the minimum incoming message magnitude during check-node (CN) processing, at the cost of systematic message magnitude overestimation. The scaled MS (SMS) decoder compensates for this effect using a fixed scaling factor. We propose the syndrome adaptive gain Min-Sum (SAGMS) decoder for quantum low-density parity-check (QLDPC) codes, which adapts the message gain online based on the fraction of unsatisfied stabilizers, requiring no per-code or per-noise level optimization. We show that the scaling factor required for SMS to match belief propagation decreases with the CN degree, so any fixed scaling optimized for one degree incurs into a growing penalty as the CN degree varies. SAGMS avoids this limitation by adapting the gain during decoding. Simulations on generalized bicycle QLDPC codes demonstrate that SAGMS matches or outperforms the frame error rate (FER) of an offline optimized SMS decoder. Moreover, SAGMS approaches BP performance and, under certain conditions outperforms it while retaining MS-level complexity.

arXiv:2605.10433•May 11, 2026•0 citations

A Weighted Belief Propagation Decoding Algorithm of LDPC Codes for Fast Convergence and Early Stopping

Tso-Cho Chen

A weighted belief propagation decoding algorithm for low-density parity-check decoding is proposed to accelerate the convergence of decoding and reduce the number of decoding iterations. We propose an early stopping criterion which is based on the average weighted reliability measure of the hard output of decoder to detect undecodable blocks in an early stage of the decoding process. In addition, an adaptive weighted iteration scheme is proposed to increase the convergence speed of belief propagation (BP) decoding and therefore improve the error performance. The evolution of the adaptive weighting factor with the number of decoding iterations is based on the relative entropy between two consecutive ”a posteriori” probabilities distribution at decoder output. Simulation results show that the proposed algorithm can achieve about 0.2-0.4 dB coding gain improvement on average while reducing up to about 50%-85% iterations for decoding at low to medium E(subscript b)/ N(subscript 0) , compared with the conventional BP based algorithms.

•Jul 1, 2012•0 citations
This paper proposes two approaches for reducing the impact of the error floor phenomenon when decoding quantum low-density parity-check codes with belief propagation based algorithms. First, a low-complexity syndrome-based linear programming (SB- LP) decoding algorithm is proposed, and second, the proposed SB-LP is applied as a post-processing step after syndrome-based min-sum (SB-MS) decoding. For the latter case, a new early stopping criterion is introduced to decide when to activate the SB- LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for a sample hypergraph code, that the proposed decoder can lower the error floor by two to three orders of magnitude compared to SB-MS for the same total number of decoding iterations.
This paper proposes a novel low-complexity syndrome-based linear programming (SB-LP) decoding algorithm for decoding quantum low-density parity-check (LDPC) codes. Under the code-capacity model, the SB-LP decoder can be used as a standalone decoder; however, it is particularly powerful when used as a post-processing step following syndrome-based min-sum (SB-MS) decoding. In the latter case, the proposed decoder is shown to be capable of significantly reducing the error floor of the SB-MS decoder for both flooded and layered SB-MS scheduling. Also, an early stopping criterion is introduced to decide when to activate the SB-LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for some example hypergraph and generalized bicycle (GB) codes, that the proposed decoder can lower the error floor by one to three orders of magnitude compared to SB-MS for the same total number of decoding iterations. Furthermore, for the class of GB codes, it is shown that as the minimum distance of the code increases, the logical error rate provided by the proposed decoder also improves, indicating that the solution is scalable. Under the circuit-level noise model, it is shown that while the SB-LP decoder does not fully replace the need for ordered statistics decoding (OSD) when flooded SB-MS is used as a preliminary step, it reduces the number of calls to the OSD post-processor, which directly impacts the overall latency. Additionally, the method offers a syndrome-matching decoder and improves the accuracy of the logical error rate for bivariate bicycle codes of distances six to eighteen, particularly at low error rates, when compared to the BP+OSD benchmark.
A two-stage decoding algorithm to lower the error-floor for low-density parity-check (LDPC) codes is presented. An efficient stopping criterion is proposed to avoid unnecessary iterations in the first stage. If the stopping criterion is reached, the first stage decoding will be terminated and the second stage decoding will be started, where the unsuccessfully decoded words are re-decoded by manipulating the log-likelihood ratio (LLR) of two types of specifically selected variable nodes. Simulation results show that the proposed algorithm can effectively lower the error floor of LDPC codes while maintaining a low decoding complexity.
Quantum processors need to improve their reliability to scale up the number of qubits and increase the number of algorithms that can execute. To reduce the logical error rate of the quantum systems, the use of error correction codes and decoders has been established as a low-cost and feasible approach, with good results from a theoretical perspective, for mid and long-term architectures. While most of the authors are focused on the algorithms to improve the correction capability of quantum computers, without taking into account a fundamental implementation aspect for their deployment in a real system, i.e., their latency must be bounded to avoid the qubit decoherence, only a few propose hardware architectures and they just include time estimations of their decoding latency. However, a real implementation has not been shown yet. In this work, we analyze from the point of view of hardware implementation two algorithmic options based on quantum low-density parity-check (QLDPC) codes: a) belief propagation min-sum decoders combined with codes with good error-floor behavior and b) belief propagation min-sum decoders concatenated with ordered statistics decoders (OSDs) for codes with early error-floor. The bounds for the maximum clock frequency required by the decoders to decode within the qubit coherence time are established as a parameter to show if a practical implementation is possible with the present or near future FPGA technology. Furthermore, real implementation results for a Xilinx FPGA device are provided, showing that some solutions can meet the timing constraints set up by the state-of-the-art quantum processors.
A two stage belief-propagation(TSBP) decoding algorithm was developed based on trapping set state(TSS) detection to reduce the error floor of low-density parity-check(LDPC) codes.The algorithm uses belief-propagation algorithm until the TSS is detected,then iterative decoding is attempted to continue through flipping and augmenting the initial values of the possible error bits until the decoding succeeds or the maximum number of attempts is reached.Simulations show that the algorithm significantly reduces the maximum number of iterations for decoding in the error floor region,and with a few additional attempts,the error floor of LDPC codes can be reduced by nearly two orders of magnitude.
Min-Sum (MS) decoding is a popular low-complexity alternative to belief propagation (BP), retaining only the minimum incoming message magnitude during check-node (CN) processing, at the cost of systematic message magnitude overestimation. The scaled MS (SMS) decoder compensates for this effect using a fixed scaling factor. We propose the syndrome adaptive gain Min-Sum (SAGMS) decoder for quantum low-density parity-check (QLDPC) codes, which adapts the message gain online based on the fraction of unsatisfied stabilizers, requiring no per-code or per-noise level optimization. We show that the scaling factor required for SMS to match belief propagation decreases with the CN degree, so any fixed scaling optimized for one degree incurs into a growing penalty as the CN degree varies. SAGMS avoids this limitation by adapting the gain during decoding. Simulations on generalized bicycle QLDPC codes demonstrate that SAGMS matches or outperforms the frame error rate (FER) of an offline optimized SMS decoder. Moreover, SAGMS approaches BP performance and, under certain conditions outperforms it while retaining MS-level complexity.
A weighted belief propagation decoding algorithm for low-density parity-check decoding is proposed to accelerate the convergence of decoding and reduce the number of decoding iterations. We propose an early stopping criterion which is based on the average weighted reliability measure of the hard output of decoder to detect undecodable blocks in an early stage of the decoding process. In addition, an adaptive weighted iteration scheme is proposed to increase the convergence speed of belief propagation (BP) decoding and therefore improve the error performance. The evolution of the adaptive weighting factor with the number of decoding iterations is based on the relative entropy between two consecutive ”a posteriori” probabilities distribution at decoder output. Simulation results show that the proposed algorithm can achieve about 0.2-0.4 dB coding gain improvement on average while reducing up to about 50%-85% iterations for decoding at low to medium E(subscript b)/ N(subscript 0) , compared with the conventional BP based algorithms.