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

IEEE Transactions on Quantum Engineering

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

Sana Javed, Sergio Colet, Francisco García-Herrero, Óscar Ruano, Juan Antonio Maestro, Bane Vasić, Mark F. Flanagan

Published Dec 4, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/tqe.2025.3640361

Related papers

Low-Complexity Linear Programming Based Decoding of Quantum LDPC Codes

Sana Javed, Francisco García-Herrero, Bane V. Vasic +1 more

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.

arXiv:2311.18488•International Conference on Communications•Jun 9, 2024•5 citations

Adaptive decoding of quantum LDPC codes through decoder disagreement

Maida Wang, Peter V. Coveney

Accurate decoding of quantum low-density parity-check (qLDPC) codes often relies on expensive post-processing search, although decoding difficulty varies strongly between syndromes. We find that the benefit of deeper post-processing search is highly concentrated in a small subset of decoding instances, and that these instances can be identified directly from the decoder itself. To this end, we introduce an adaptive decoder based on belief propagation (BP) and ordered-statistics decoding (OSD), using the disagreement between the BP hard decision and the syndrome-consistent order-zero OSD solution as an internal risk signal to determine where deeper search is required. On a $[[144,12,12]]$ bivariate bicycle code under circuit-level depolarising noise, encoding $12$ logical qubits in $144$ data qubits with distance $12$, escalating only the highest-risk $20\%$ of instances recovers $85\%$ to $92\%$ of the improvement in logical error rate available from a full one-free-variable sweep, while reducing the mean serial decoding cost by a factor of $3.6$ relative to applying the same truncated search to every instance. At matched budget, disagreement-guided routing also outperforms routing based on the BP syndrome residual, syndrome weight and random selection. The same behaviour reappears on a structurally distinct radial qLDPC code obtained from a lifted-product construction, where escalating $20\%$ of instances recovers $87\%$ to $94\%$ of the available gain. A $Z$-memory experiment on the Quantinuum H2 trapped-ion processor, implementing both $X$-type and $Z$-type checks, further shows that the signal remains predictive under device noise. These results show that decoder-internal disagreement can expose where additional decoding effort is valuable, allowing classical computation to be concentrated on the instances most likely to benefit from it.

quant-pharXiv:2609.37629•Sep 30, 2026•0 citations

List Decoding and New Bicycle Code Constructions for Quantum LDPC Codes

Rabeti, Sheida, Mahdavifar, Hessam

In this paper, we propose a new decoder, called the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), for Quantum Low-Density Parity-Check (QLDPC) codes. It extends the Multiple-Bases Belief-Propagation (MBBP) framework, originally developed for classical cyclic LDPC codes. The proposed method preserves the linear-time complexity of standard BP decoder while improving the logical error rate. To further reduce the logical error rate, a new decision rule is introduced for the post-processing list decoder, outperforming the conventional least-metric selector (LMS) criterion. For the recently developed and implemented bivariate bicycle (BB) code with parameters \([[144,12,12]]\), our proposed MBBP-LD decoder achieves up to 40\% lower logical error rate compared to the state-of-the-art decoder for short QLDPC codes, i.e., BP with ordered-statistics decoding (BP-OSD), while retaining the linear-time complexity of the plain BP decoder. In addition, we explore a new subclass of BB codes, that we refer to as the univariate bicycle (UB) codes, specifically with lower-weight parity checks (\(w=6,8\)). This reduces the polynomial search space for the code compared to general BB codes, i.e., by reducing the search space over two polynomial components in BB codes to just a single polynomial component in UB codes. Simulations demonstrate the promising performance of these codes under various types of BP decoders.

arXiv:2511.02951•Nov 4, 2025•0 citations

Beam search decoder for quantum LDPC codes

Min Ye, Dave Wecker, Nicolas Delfosse

We propose a decoder for quantum low density parity check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the $[[144, 12, 12]]$ bivariate bicycle (BB) code at noise rate $p=10^{-3}$ to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a $17\times$ reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a $26.2\times$ reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a $5.6\times$ reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1ms at $p=5 \times10^{-4}$. Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.

quant-pharXiv:2512.07057•Dec 9, 2025•0 citations

Beam Search Decoder for Quantum Low-Density Parity-Check Codes

Min Ye, Dave Wecker, Nicolas Delfosse

We propose a decoder for quantum low-density parity-check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the [ [ 144 , 12 , 12 ] ] bivariate bicycle (BB) code at noise rate p = 10 − 3 to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a 17 × reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a 26.2 × reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a 5.6 × reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1 ms at p = 5 × 10 − 4 . Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.

PRX Quantum•May 26, 2026•0 citations

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•0 citations
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.
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.
Accurate decoding of quantum low-density parity-check (qLDPC) codes often relies on expensive post-processing search, although decoding difficulty varies strongly between syndromes. We find that the benefit of deeper post-processing search is highly concentrated in a small subset of decoding instances, and that these instances can be identified directly from the decoder itself. To this end, we introduce an adaptive decoder based on belief propagation (BP) and ordered-statistics decoding (OSD), using the disagreement between the BP hard decision and the syndrome-consistent order-zero OSD solution as an internal risk signal to determine where deeper search is required. On a [[144,12,12]][[144,12,12]][[144,12,12]] bivariate bicycle code under circuit-level depolarising noise, encoding 121212 logical qubits in 144144144 data qubits with distance 121212, escalating only the highest-risk 20%20\%20% of instances recovers 85%85\%85% to 92%92\%92% of the improvement in logical error rate available from a full one-free-variable sweep, while reducing the mean serial decoding cost by a factor of 3.63.63.6 relative to applying the same truncated search to every instance. At matched budget, disagreement-guided routing also outperforms routing based on the BP syndrome residual, syndrome weight and random selection. The same behaviour reappears on a structurally distinct radial qLDPC code obtained from a lifted-product construction, where escalating 20%20\%20% of instances recovers 87%87\%87% to 94%94\%94% of the available gain. A ZZZ-memory experiment on the Quantinuum H2 trapped-ion processor, implementing both XXX-type and ZZZ-type checks, further shows that the signal remains predictive under device noise. These results show that decoder-internal disagreement can expose where additional decoding effort is valuable, allowing classical computation to be concentrated on the instances most likely to benefit from it.
In this paper, we propose a new decoder, called the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), for Quantum Low-Density Parity-Check (QLDPC) codes. It extends the Multiple-Bases Belief-Propagation (MBBP) framework, originally developed for classical cyclic LDPC codes. The proposed method preserves the linear-time complexity of standard BP decoder while improving the logical error rate. To further reduce the logical error rate, a new decision rule is introduced for the post-processing list decoder, outperforming the conventional least-metric selector (LMS) criterion. For the recently developed and implemented bivariate bicycle (BB) code with parameters [[144,12,12]][[144,12,12]][[144,12,12]], our proposed MBBP-LD decoder achieves up to 40\% lower logical error rate compared to the state-of-the-art decoder for short QLDPC codes, i.e., BP with ordered-statistics decoding (BP-OSD), while retaining the linear-time complexity of the plain BP decoder. In addition, we explore a new subclass of BB codes, that we refer to as the univariate bicycle (UB) codes, specifically with lower-weight parity checks (w=6,8w=6,8w=6,8). This reduces the polynomial search space for the code compared to general BB codes, i.e., by reducing the search space over two polynomial components in BB codes to just a single polynomial component in UB codes. Simulations demonstrate the promising performance of these codes under various types of BP decoders.
We propose a decoder for quantum low density parity check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the [[144,12,12]][[144, 12, 12]][[144,12,12]] bivariate bicycle (BB) code at noise rate p=10−3p=10^{-3}p=10−3 to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a 17×17\times17× reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a 26.2×26.2\times26.2× reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a 5.6×5.6\times5.6× reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1ms at p=5×10−4p=5 \times10^{-4}p=5×10−4. Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.
We propose a decoder for quantum low-density parity-check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the [ [ 144 , 12 , 12 ] ] bivariate bicycle (BB) code at noise rate p = 10 − 3 to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a 17 × reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a 26.2 × reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a 5.6 × reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1 ms at p = 5 × 10 − 4 . Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.
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.