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:2605.14170

Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

Sheida Rabeti, Hessam Mahdavifar

Published May 13, 2026• 0 citations
arXivHTMLPDF

Abstract

In this paper, we propose a belief-propagation (BP)-based decoder, termed the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), for quantum low-density parity-check (QLDPC) codes. The key idea is to generate \emph{structured decoding diversity} by constructing multiple redundant parity-check representations via cycle-free subtree decompositions of the Tanner graph, and running BP decoding in parallel across these representations. This extends the classical Multiple-Bases Belief-Propagation (MBBP) framework to the quantum setting while preserving the linear-time complexity and efficiency of standard BP decoding, and avoids the need for super-linear post-processing. Simulation results demonstrate that MBBP-LD improves upon existing BP-based decoders, including BP with ordered statistics decoding (BP-OSD) and belief propagation with guided decimation (BPGD) across several QLDPC codes, while requiring substantially fewer total BP iterations. For bivariate bicycle codes $[[144,12,12]]$ and $[[288,12,18]]$, MBBP-LD achieves up to $20\%$ reduction in error rate compared to BPGD and up to $30\%$ compared to BP-OSD in the low- and moderate-error regimes. For the larger B1 code $[[882, 24, 18 \leq d \leq 24]]$, MBBP-LD attains comparable or improved performance relative to BPGD while maintaining BP-like decoding latency under parallel implementation.

DOI
10.48550/arxiv.2605.14170

Related papers

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

Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation

Hanwen Yao, Waleed Abu Laban, Christian Häger +2 more

Quantum low-density parity-check (QLDPC) codes have emerged as a promising technique for quantum error correction. A variety of decoders have been proposed for QLDPC codes and many utilize belief propagation (BP) decoding in some fashion. However, the use of BP decoding for degenerate QLDPC codes is known to have issues with convergence. These issues are typically attributed to short cycles in the Tanner graph and error patterns with the same syndrome due to code degeneracy. In this work, we propose a decoder for QLDPC codes based on BP guided decimation (BPGD), which has been previously studied for constraint satisfaction and lossy compression problems. This decimation process is applicable to both binary and quaternary BP and it involves sequentially freezing the value of the most reliable qubits to encourage BP convergence. We find that BPGD significantly reduces the BP failure rate due to non-convergence, achieving performance on par with BP with ordered statistics decoding and BP with stabilizer inactivation, without the need to solve systems of linear equations. To explore how and why BPGD improves performance, we discuss several interpretations of BPGD and their connection to BP syndrome decoding.

arXiv:2312.10950•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•29 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

Decimation Strategies for Belief Propagation Decoding of Quantum LDPC Codes

Masoumeh Alinia, David G. M. Mitchell, Hanwen Yao +1 more

Due to code degeneracy and the graph structure of quantum low-density parity-check (QLDPC) codes, the performance of conventional belief propagation (BP) decoding can be poor. Recently, belief propagation guided decimation (BPGD) has shown promise to combat these challenges. In this paper, we investigate various decimation approaches to improve the error correcting performance and convergence speed of BPGD. We first consider soft decimation, where the BP equations are modified via several tuneable parameters. This approach exhibits linear complexity relative to the length of the block code and is shown to outperform hard decimation approaches for careful selection of the algorithm parameters. We then combine the approaches in a "soft-hard" BPGD variant, where hard decisions are periodically made and those symbols are permanently fixed throughout the remainder of the decoding process. Simulation results show that further performance improvement can be observed in this case at the cost of increasing the algorithmic complexity.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•1 citation

Sequential BP-based Decoding of QLDPC Codes

Mohsen Moradi, Salman Habib, Vahid Nourozi +1 more

Quantum low-density parity-check (QLDPC) codes are a leading approach to quantum error correction, yet conventional belief propagation (BP) decoders often perform poorly, primarily due to non-convergence exacerbated by stabilizer constraints, which induce short cycles and degeneracy. We propose two scheduling variants, sequential check node scheduling (SCNS) and sequential variable node scheduling (SVNS), that improve BP's error-correction ability by processing check nodes (CNs) or variable nodes (VNs), respectively, in a fixed order, stabilizing message updates and reducing stalls. We also employ this technique to an improved BP-variant called BP guided decimation (BPGD), where symbols are progressively fixed during decoding iterations. Here, we demonstrate that the sequential BPGD (SBPGD) decoder can further improve the convergence properties and performance of the decoder. On standard QLDPC benchmarks under a Pauli-X noise model, our sequential schedules are shown to lower the block error rate relative to conventional BP, and SBPGD outperforms BPGD while using significantly fewer decimation rounds, translating to lower computational cost. These results demonstrate that changing the update schedule, without altering the code, can improve both the reliability and efficiency of BP-based decoding for QLDPC codes. For the [[1922,50,16]] C2 hypergraph-product code with independent X errors, SVNS-BP surpasses BP-OSD-0 in error correction at roughly the same complexity as standard BP.

arXiv:2602.13420•Feb 13, 2026•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
In this paper, we propose a belief-propagation (BP)-based decoder, termed the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), for quantum low-density parity-check (QLDPC) codes. The key idea is to generate \emph{structured decoding diversity} by constructing multiple redundant parity-check representations via cycle-free subtree decompositions of the Tanner graph, and running BP decoding in parallel across these representations. This extends the classical Multiple-Bases Belief-Propagation (MBBP) framework to the quantum setting while preserving the linear-time complexity and efficiency of standard BP decoding, and avoids the need for super-linear post-processing. Simulation results demonstrate that MBBP-LD improves upon existing BP-based decoders, including BP with ordered statistics decoding (BP-OSD) and belief propagation with guided decimation (BPGD) across several QLDPC codes, while requiring substantially fewer total BP iterations. For bivariate bicycle codes [[144,12,12]][[144,12,12]][[144,12,12]] and [[288,12,18]][[288,12,18]][[288,12,18]], MBBP-LD achieves up to 20%20\%20% reduction in error rate compared to BPGD and up to 30%30\%30% compared to BP-OSD in the low- and moderate-error regimes. For the larger B1 code [[882,24,18≤d≤24]][[882, 24, 18 \leq d \leq 24]][[882,24,18≤d≤24]], MBBP-LD attains comparable or improved performance relative to BPGD while maintaining BP-like decoding latency under parallel implementation.
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.
Quantum low-density parity-check (QLDPC) codes have emerged as a promising technique for quantum error correction. A variety of decoders have been proposed for QLDPC codes and many utilize belief propagation (BP) decoding in some fashion. However, the use of BP decoding for degenerate QLDPC codes is known to have issues with convergence. These issues are typically attributed to short cycles in the Tanner graph and error patterns with the same syndrome due to code degeneracy. In this work, we propose a decoder for QLDPC codes based on BP guided decimation (BPGD), which has been previously studied for constraint satisfaction and lossy compression problems. This decimation process is applicable to both binary and quaternary BP and it involves sequentially freezing the value of the most reliable qubits to encourage BP convergence. We find that BPGD significantly reduces the BP failure rate due to non-convergence, achieving performance on par with BP with ordered statistics decoding and BP with stabilizer inactivation, without the need to solve systems of linear equations. To explore how and why BPGD improves performance, we discuss several interpretations of BPGD and their connection to BP syndrome decoding.
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.
Due to code degeneracy and the graph structure of quantum low-density parity-check (QLDPC) codes, the performance of conventional belief propagation (BP) decoding can be poor. Recently, belief propagation guided decimation (BPGD) has shown promise to combat these challenges. In this paper, we investigate various decimation approaches to improve the error correcting performance and convergence speed of BPGD. We first consider soft decimation, where the BP equations are modified via several tuneable parameters. This approach exhibits linear complexity relative to the length of the block code and is shown to outperform hard decimation approaches for careful selection of the algorithm parameters. We then combine the approaches in a "soft-hard" BPGD variant, where hard decisions are periodically made and those symbols are permanently fixed throughout the remainder of the decoding process. Simulation results show that further performance improvement can be observed in this case at the cost of increasing the algorithmic complexity.
Quantum low-density parity-check (QLDPC) codes are a leading approach to quantum error correction, yet conventional belief propagation (BP) decoders often perform poorly, primarily due to non-convergence exacerbated by stabilizer constraints, which induce short cycles and degeneracy. We propose two scheduling variants, sequential check node scheduling (SCNS) and sequential variable node scheduling (SVNS), that improve BP's error-correction ability by processing check nodes (CNs) or variable nodes (VNs), respectively, in a fixed order, stabilizing message updates and reducing stalls. We also employ this technique to an improved BP-variant called BP guided decimation (BPGD), where symbols are progressively fixed during decoding iterations. Here, we demonstrate that the sequential BPGD (SBPGD) decoder can further improve the convergence properties and performance of the decoder. On standard QLDPC benchmarks under a Pauli-X noise model, our sequential schedules are shown to lower the block error rate relative to conventional BP, and SBPGD outperforms BPGD while using significantly fewer decimation rounds, translating to lower computational cost. These results demonstrate that changing the update schedule, without altering the code, can improve both the reliability and efficiency of BP-based decoding for QLDPC codes. For the [[1922,50,16]] C2 hypergraph-product code with independent X errors, SVNS-BP surpasses BP-OSD-0 in error correction at roughly the same complexity as standard BP.
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.