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

Decoding with alternating weighted graph sparsification for quantum low-density parity-check codes

Josu Etxezarreta Martinez, Francisco Garcia-Herrero, Ruben M. Otxoa, Reza Dastbasteh

quant-phSubmitted Oct 26, 2026• Announced Oct 27, 2026• 0 citations
arXivHTMLPDF

Abstract

Real-time decoding is a fundamental necessity for building fault-tolerant quantum computers. In this work, we introduce decoding with alternating weighted graph sparsification (DAWG), an ensemble based approach that combines Tanner graph sparsification with ensembling belief-propagation (BP) decoders. The DAWG decoder runs BP decoders over the full detector error model Tanner graph for certain iterations to then transfer the posteriors to a sparsified graph in which additional rounds of BP are run. Each of the decoders in the ensemble uses a different transfer matrix to map the posterior information to the sparsified graph. We use the serial schedule for the minimum-sum BP decoders and, thus, employ Vibe decoding ideas by randomizing the schedules of each of them. The performance of the DAWG decoder is then numerically studied for bivariate bicycle codes and superdense color code circuits to be compared with other state-of-the-art decoding approaches. Importantly, the DAWG decoder shows a similar performance to Relay belief-propagation and Vibe decoding when combined with an order-$0$ Localized Statistics Decoding (LSD-$0$) post-processor. Crucially, the post-processor is called an order of magnitude less times than for Vibe with the same ensemble size, indicating that the introduced latency tail will be minimal. Furthermore, LSD-$0$ operates on a sparsified decoding graph of a fraction of the size of the full detector error model, which simplifies the resources required by specialized hardware to support it. Overall, the DAWG+LSD-$0$ decoder represents a viable low-cost BP-based decoding algorithm for quantum error correction codes.

AI Summary

The paper addresses circuit-level decoding of qLDPC codes, focusing on reducing belief-propagation (BP) failures and reliance on slower post-processing. Decoding with alternating weighted graph sparsification (DAWG) runs an ensemble of randomized serial BP decoders on the full detector error model (DEM), transfers unconverged posterior information to a sparsified DEM using different transfer matrices, and runs further BP iterations. Remaining failures are processed by order-zero localized statistics decoding (LSD-$0$) on the sparsified graph. Monte Carlo simulations under circuit-level depolarizing noise cover three bivariate bicycle codes through $[[144,12,12]]$ and superdense color-code circuits with distances $3,5,7,9$. With 20 total BP iterations and ensembles of 5–20 decoders, DAWG+LSD-$0$ matches reported RelayBP logical-error performance for the Gross code using uncorrelated DEMs, and reported Vibe+LSD-$0$ performance for color codes using correlated DEMs. For color codes, DAWG uses at most 15 ensemble members versus 32 in the reported Vibe results. At matched ensemble sizes and iteration counts, post-processing is invoked up to an order of magnitude less often than with Vibe. Sparsified graphs retain roughly 10–31% of full-DEM variable nodes. Architecture-based estimates, rather than a hardware demonstration, predict 7–40-fold lower worst-case latency than full-DEM BP+OSD-$0$. Stated limitations include transfer matrices found through restricted exhaustive search, unoptimized hardware and deterministic schedules, and untested decoding of logical operations. Efficient transfer-matrix generation, sparsified-model selection, and scalability to larger codes remain open implementation questions.

Little sign of AI-generated textOverclaims

Error found: Reduced post-processor invocation frequency and architectural latency estimates support potential latency improvements, but do not establish the abstract's claim of minimal end-to-end latency tails. The reported order-of-magnitude reduction in post-processing calls is supported for selected codes and low-error regimes, not as an unqualified property of DAWG. The BB sparsified graphs contain approximately 11.3%, 31.4%, and 31.1% of the original variable nodes, rather than uniformly containing 25%. The latency table implies worst-case speedups of approximately 3.76–32.76 over full-DEM BP+OSD-0, contradicting the stated 7–40-fold range.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
13 pages, 5 figures

Related papers

An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

Antonio deMarti iOlius, Imanol Etxezarreta Martinez, Joschka Roffe +1 more

Abstract Fault-tolerant quantum computers must be designed in conjunction with classical co-processors that decode quantum error correction measurement information in real-time. In this work, we introduce the belief propagation plus ordered Tanner forest (BP + OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes. The OTF post-processing stage removes qubits from the decoding graph until it has a tree-like structure. Provided that the resultant loop-free OTF graph supports a subset of qubits that can generate the syndrome, BP decoding is then guaranteed to converge. To enhance performance under circuit-level noise, we introduce a technique for sparsifying detector error models. This method uses a transfer matrix to map soft information from the full detector graph to the sparsified graph, preserving critical error propagation information from the syndrome extraction circuit. Our BP+OTF implementation first applies standard BP to the full detector graph, followed by BP + OTF post-processing on the sparsified graph. Numerical simulations show that the BP+OTF decoder achieves similar logical error suppression compared to state-of-the-art inversion-based and matching decoders for bivariate bicycle and surface codes, respectively, while maintaining almost-linear runtime complexity across all stages.

arXiv:2409.01440•npj Quantum Information•Jun 9, 2026•4 citations

Belief Propagation Decoding for Short-Length Codes Based on Sparse Tanner Graph

Zongyao Li, Yifei Shen, Yuqing Ren +3 more

In this paper, we present a novel approach to improve belief propagation (BP) decoding performance by sparsifying the Tanner graph. Our proposed method first constructs a low-weight parity-check (LWPC) matrix with increased rows based on the original parity-check matrix. Then, all 4-cycles in the LWPC matrix are eliminated by adding auxiliary variable nodes and corresponding parity-check rows, resulting in the generalized LWPC (G-LWPC) matrix. Compared to the original matrix, the sparsity is greatly improved without altering the encoding constraints. Simulation results show that BP decoding based on the G-LWPC matrix is particularly effective for short code lengths. For a (128,20) polar code with 24-bit cyclic redundancy check, our proposed G-LWPC matrix reduces the density from 17.4% to 1.3%, and with 10 iterations, BP decoding can achieve the performance of successive cancellation list decoding with a list size of 32.

IEEE Communications Letters•Feb 14, 2024•8 citations

Accelerating BP-based decoders for QLDPC Codes with Local Syndrome-Based Preprocessing

Fan, Wenxuan, Yasunari Suzuki, Gokul Subramanian Ravi +4 more

Due to the high error rate of qubits, detecting and correcting errors is essential for achieving fault-tolerant quantum computing (FTQC). Quantum low-density parity-check (QLDPC) codes are one of the most promising quantum error correction (QEC) methods due to their high encoding rates. BP (Belief Propagation)-based decoders are widely used and highly competitive for QLDPC codes because BP offers inherent parallelism and strong scalability. However, BP-based decoders still suffer from high decoding latency, a large portion of which is spent in the iterative BP stage. In this paper, we propose a lightweight preprocessing step that utilizes local patterns in the syndrome to detect likely trivial error events and provide them as hints to BP-based decoders. These hints accelerate BP convergence and thereby reduce the overall decoding time. The proposed preprocessing step offers a broadly compatible approach to reducing the latency of BP-based QLDPC decodes. On the bivariate bicycle code $[[144,12,12]]$ at low physical error rates, our method achieves a $10\times$ speedup in decoding time for BP-OSD, and more than $2\times$ speedup for both BP-LSD and Relay-BP. Our method maintains the logical error rate when combined with BP-OSD and Relay-BP, while further achieving a significant reduction in logical error rate when combined with BP-LSD.

arXiv:2509.01892•Sep 2, 2025•0 citations

GPU-Based Parallel BP Decoding for Quantum LDPC Memory

Ming Wang, Yanbo Zhao, Ang Li +1 more

Quantum low-density parity-check (qLDPC) decoding requires reliable corrections and low latency over long syndrome histories. We extend BP-SF, an oscillation-guided belief-propagation (BP) decoder with independent syndrome-flip trials, by introducing windowed and streaming operations. Our CUDA implementation combines disordered-memory retries, sliding windows, correlation-aware graphs, and layered scheduling. Circuit-level simulations test fixed-basis memory and complete logical Pauli-frame recovery. On the [[144,12,12]] bivariate bicycle code at physical error rate p = 0.002, parallel BP-SF reduces 99.9th-percentile call latency by a factor of 13.15 relative to an eight-chain Relay-BP GPU baseline on 100,000 matched samples for which every tested method's initial BP stage fails within 80 iterations. Windowed BP-SF maintains a flat logical error rate and nearly constant per-round compute time through 512 rounds, reaching a 17.1-fold speedup over monolithic decoding. In 512-round full-frame streaming decoding with 2.97-ms syndrome arrivals, layered BP-SF on a transformed joint graph with 20 retries reduces 99.9th-percentile correction-release age from 166.29 to 36.25 ms relative to the joint graph with flooding updates and 100 retries. These results connect parallel BP post-processing to lower decoding costs and earlier correction release in streaming quantum memory.

quant-pharXiv:2610.13879•Oct 12, 2026•0 citations

Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

Sheida Rabeti, Hessam Mahdavifar

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.

arXiv:2605.14170•May 13, 2026•0 citations

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•8 citations
Real-time decoding is a fundamental necessity for building fault-tolerant quantum computers. In this work, we introduce decoding with alternating weighted graph sparsification (DAWG), an ensemble based approach that combines Tanner graph sparsification with ensembling belief-propagation (BP) decoders. The DAWG decoder runs BP decoders over the full detector error model Tanner graph for certain iterations to then transfer the posteriors to a sparsified graph in which additional rounds of BP are run. Each of the decoders in the ensemble uses a different transfer matrix to map the posterior information to the sparsified graph. We use the serial schedule for the minimum-sum BP decoders and, thus, employ Vibe decoding ideas by randomizing the schedules of each of them. The performance of the DAWG decoder is then numerically studied for bivariate bicycle codes and superdense color code circuits to be compared with other state-of-the-art decoding approaches. Importantly, the DAWG decoder shows a similar performance to Relay belief-propagation and Vibe decoding when combined with an order-000 Localized Statistics Decoding (LSD-000) post-processor. Crucially, the post-processor is called an order of magnitude less times than for Vibe with the same ensemble size, indicating that the introduced latency tail will be minimal. Furthermore, LSD-000 operates on a sparsified decoding graph of a fraction of the size of the full detector error model, which simplifies the resources required by specialized hardware to support it. Overall, the DAWG+LSD-000 decoder represents a viable low-cost BP-based decoding algorithm for quantum error correction codes.
The paper addresses circuit-level decoding of qLDPC codes, focusing on reducing belief-propagation (BP) failures and reliance on slower post-processing. Decoding with alternating weighted graph sparsification (DAWG) runs an ensemble of randomized serial BP decoders on the full detector error model (DEM), transfers unconverged posterior information to a sparsified DEM using different transfer matrices, and runs further BP iterations. Remaining failures are processed by order-zero localized statistics decoding (LSD-000) on the sparsified graph.
Monte Carlo simulations under circuit-level depolarizing noise cover three bivariate bicycle codes through [[144,12,12]][[144,12,12]][[144,12,12]] and superdense color-code circuits with distances 3,5,7,93,5,7,93,5,7,9. With 20 total BP iterations and ensembles of 5–20 decoders, DAWG+LSD-000 matches reported RelayBP logical-error performance for the Gross code using uncorrelated DEMs, and reported Vibe+LSD-000 performance for color codes using correlated DEMs. For color codes, DAWG uses at most 15 ensemble members versus 32 in the reported Vibe results. At matched ensemble sizes and iteration counts, post-processing is invoked up to an order of magnitude less often than with Vibe. Sparsified graphs retain roughly 10–31% of full-DEM variable nodes.
Architecture-based estimates, rather than a hardware demonstration, predict 7–40-fold lower worst-case latency than full-DEM BP+OSD-000. Stated limitations include transfer matrices found through restricted exhaustive search, unoptimized hardware and deterministic schedules, and untested decoding of logical operations. Efficient transfer-matrix generation, sparsified-model selection, and scalability to larger codes remain open implementation questions.
Abstract Fault-tolerant quantum computers must be designed in conjunction with classical co-processors that decode quantum error correction measurement information in real-time. In this work, we introduce the belief propagation plus ordered Tanner forest (BP + OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes. The OTF post-processing stage removes qubits from the decoding graph until it has a tree-like structure. Provided that the resultant loop-free OTF graph supports a subset of qubits that can generate the syndrome, BP decoding is then guaranteed to converge. To enhance performance under circuit-level noise, we introduce a technique for sparsifying detector error models. This method uses a transfer matrix to map soft information from the full detector graph to the sparsified graph, preserving critical error propagation information from the syndrome extraction circuit. Our BP+OTF implementation first applies standard BP to the full detector graph, followed by BP + OTF post-processing on the sparsified graph. Numerical simulations show that the BP+OTF decoder achieves similar logical error suppression compared to state-of-the-art inversion-based and matching decoders for bivariate bicycle and surface codes, respectively, while maintaining almost-linear runtime complexity across all stages.
In this paper, we present a novel approach to improve belief propagation (BP) decoding performance by sparsifying the Tanner graph. Our proposed method first constructs a low-weight parity-check (LWPC) matrix with increased rows based on the original parity-check matrix. Then, all 4-cycles in the LWPC matrix are eliminated by adding auxiliary variable nodes and corresponding parity-check rows, resulting in the generalized LWPC (G-LWPC) matrix. Compared to the original matrix, the sparsity is greatly improved without altering the encoding constraints. Simulation results show that BP decoding based on the G-LWPC matrix is particularly effective for short code lengths. For a (128,20) polar code with 24-bit cyclic redundancy check, our proposed G-LWPC matrix reduces the density from 17.4% to 1.3%, and with 10 iterations, BP decoding can achieve the performance of successive cancellation list decoding with a list size of 32.
Due to the high error rate of qubits, detecting and correcting errors is essential for achieving fault-tolerant quantum computing (FTQC). Quantum low-density parity-check (QLDPC) codes are one of the most promising quantum error correction (QEC) methods due to their high encoding rates. BP (Belief Propagation)-based decoders are widely used and highly competitive for QLDPC codes because BP offers inherent parallelism and strong scalability. However, BP-based decoders still suffer from high decoding latency, a large portion of which is spent in the iterative BP stage. In this paper, we propose a lightweight preprocessing step that utilizes local patterns in the syndrome to detect likely trivial error events and provide them as hints to BP-based decoders. These hints accelerate BP convergence and thereby reduce the overall decoding time. The proposed preprocessing step offers a broadly compatible approach to reducing the latency of BP-based QLDPC decodes. On the bivariate bicycle code [[144,12,12]][[144,12,12]][[144,12,12]] at low physical error rates, our method achieves a 10×10\times10× speedup in decoding time for BP-OSD, and more than 2×2\times2× speedup for both BP-LSD and Relay-BP. Our method maintains the logical error rate when combined with BP-OSD and Relay-BP, while further achieving a significant reduction in logical error rate when combined with BP-LSD.
Quantum low-density parity-check (qLDPC) decoding requires reliable corrections and low latency over long syndrome histories. We extend BP-SF, an oscillation-guided belief-propagation (BP) decoder with independent syndrome-flip trials, by introducing windowed and streaming operations. Our CUDA implementation combines disordered-memory retries, sliding windows, correlation-aware graphs, and layered scheduling. Circuit-level simulations test fixed-basis memory and complete logical Pauli-frame recovery. On the [[144,12,12]] bivariate bicycle code at physical error rate p = 0.002, parallel BP-SF reduces 99.9th-percentile call latency by a factor of 13.15 relative to an eight-chain Relay-BP GPU baseline on 100,000 matched samples for which every tested method's initial BP stage fails within 80 iterations. Windowed BP-SF maintains a flat logical error rate and nearly constant per-round compute time through 512 rounds, reaching a 17.1-fold speedup over monolithic decoding. In 512-round full-frame streaming decoding with 2.97-ms syndrome arrivals, layered BP-SF on a transformed joint graph with 20 retries reduces 99.9th-percentile correction-release age from 166.29 to 36.25 ms relative to the joint graph with flooding updates and 100 retries. These results connect parallel BP post-processing to lower decoding costs and earlier correction release in streaming quantum memory.
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.
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.