Source-linked AI summary
GPU-Based Parallel BP Decoding for Quantum LDPC Memory
Ming Wang, Yanbo Zhao, Ang Li, Frank Mueller
TL;DR
Long qLDPC syndrome histories require reliable decoding fast enough to keep pace with syndrome extraction. This paper extends BP-SF to GPU-based windowed and streaming decoding. In the reported tests, windowing reduces per-round compute time, while layered GARI streaming reduces correction-release age relative to joint-graph flooding.
Problem
qLDPC decoders must correct errors reliably while keeping pace with syndrome extraction, but BP can oscillate on ambiguous estimates and decoding backlogs can grow.
Source: §1 · p. 1Method
The paper extends oscillation-guided BP-SF to GPU-based windowed and streaming decoding, combining posterior-initialized parallel DMem-BP retries with graph-representation and scheduling choices.
Source: §7 · p. 12Results
Windowing cuts mean compute time per round 17.1× versus monolithic decoding; full-frame GARI streaming lowers 99.9th-percentile correction-release age from 166.29 to 36.25 ms versus joint-graph flooding.
Source: §1 · p. 2, §7 · p. 12Takeaways & Limitations
Windowing supports long-memory decoding without a growing monolithic graph, but core and buffer choices trade accuracy, decoding frequency, and correction-release delay.
Source: §7 · p. 12The first-convergence rationale depends on a syndrome-consistent estimate differing from the most likely error by weight below d, which yields the same logical correction.
Source: §4 · p. 7
Abstract
from arXiv · showhide
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.
1 Introduction
qLDPC decoding must keep pace with syndrome extraction while correcting errors reliably, and BP can struggle with oscillations and trapping sets. This paper extends BP-SF to GPU-based windowed and streaming decoding and evaluates its accuracy, latency, and correction-release delay.
1 Introduction
- The introduction organizes BP-based decoding choices around message updates and scheduling, graph representation, and trial diversity, which can be combined rather than treated as separate algorithm families.The paper positions BP-SF as an ensemble approach that separates trial-input generation from message passing.Source: §1 · pp. 1–2
- The evaluation combines fixed-basis memory and complete logical Pauli-frame recovery, measuring correction-release delay as syndrome data arrive to include lookahead and computational queuing.These measures extend evaluation beyond decoding time alone.Source: §1 · p. 2
- The CUDA implementation combines posterior-initialized disordered-memory BP retries with independent BP-SF trials, extending the approach beyond its original constituent decoder.The paper also studies joint correlated-error models, the GARI transformation, and layered scheduling.Source: §1 · p. 2
- 13.15× lower 99.9th-percentile call latency than the tested eight-chain Relay-BP GPU configuration on 100,000 matched samples where every tested method’s initial BP stage fails within 80 iterations.The benchmark uses the J144, 12, 12K code at p = 0.002.Source: §1 · p. 2
- 17.1× lower mean compute time per round than monolithic decoding, while maintaining approximately constant per-round compute time and logical error rate through 512 rounds.This result is from the 144-code fixed-basis experiment.Source: §1 · p. 2
- 36.25 ms versus 166.29 ms in 99.9th-percentile correction-release age for layered BP-SF on the GARI graph with 20 retries versus joint-graph flooding with 100 retries.These are the respective configurations’ results in the 512-round long-memory experiment.Source: §1 · p. 2
2 Background
The background introduces stabilizer-code syndromes and sparse qLDPC structure, then outlines BP decoding, GARI graph transformation, and sliding-window processing.
2.1 Quantum LDPC Codes
- Stabilizer checks define the code space, and their measured outcomes form a binary syndrome used to infer a correction; code distance characterizes errors that can change encoded information without changing check outcomes.For CSS codes, separate X- and Z-type checks provide complementary error information, while Y errors correlate the two sectors.Source: §2.1 · pp. 2–3
- Bounded row and column weights give qLDPC codes a sparse representation, limiting qubit–check interactions and providing the structure used by the paper’s message-passing decoders.Each check involves a bounded number of qubits, and each qubit participates in a bounded number of checks.Source: §2.1 · p. 3
2.2 Syndrome Decoding and Belief Propagation
- BP approximates decoding by exchanging messages on a Tanner graph, but short cycles and symmetric trapping sets can deteriorate decoding or prevent convergence.The background also describes normalized min-sum updates and disordered memory BP, which mixes channel information with prior-iteration output using node-specific memory strengths.Source: §2.2 · pp. 3–4
2.3 GARI Transformation
- GARI introduces auxiliary variables and reorganizes the joint detector graph to remove four-cycles involving mixed-error variables while preserving the decoding problem.Virtual zero-syndrome checks enforce the auxiliary-variable definition.Source: §2.3 · p. 4
2.4 Sliding-Window Decoding
- A sliding window decodes an older core and newer buffer together, commits only the core estimates, and revisits tentative buffer estimates as the window advances.The buffer supplies later detector outcomes that can help resolve errors near the core boundary.Source: §2.4 · p. 5, Figure 2 · p. 5
- After a core is committed, its correction is removed from the syndrome to form the residual for the next window; streaming evaluates this relation only for detector outcomes that have arrived.Windows advance by the core length, and BP-SF trials can run in parallel within each window.Source: §2.4 · p. 5
3 BP Behavior Analysis: A Case Study
This case study examines BP convergence and hard-decision oscillations on the J144, 12, 12K code under circuit-level noise. It finds that oscillation-guided candidate selection improves decoding relative to random selection and extended BP.
3.1 Number of Iterations
- At p=0.001, BP takes a mean of 8.9 iterations, while p=0.002 lengthens the non-convergence tail; surviving samples rarely become easier with more iterations.The study uses 10,000 samples at each physical error rate and a maximum of 1,000 iterations.Source: §3.1 · p. 5, Figure 3 · p. 5
3.2 Oscillation
- At low physical error rates, oscillation identifies a subset of actual error locations with precision much higher than the raw physical error rate.Recall falls as the physical error rate rises because the number of errors grows while candidate-set size stays fixed.Source: §3.2 · pp. 5–6, Figure 4 · p. 6
- Oscillation-guided selection lowers logical error rate per round relative to random selection and BP1000, especially at low physical error rates.The comparison uses the same configured trial budget.Source: Figure 5 · p. 6, §3.2 · p. 6
4 Oscillation-Guided Syndrome-Flipping Decoding
BP-SF uses hard-decision oscillations from a failed initial BP attempt to select locations for independent syndrome-flip trials. Trials can run concurrently, and the first syndrome-valid result is mapped back to the original problem.
4 Oscillation-Guided Syndrome-Flipping Decoding
- After initial BP fails, BP-SF selects frequently oscillating bits and samples sparse trial vectors on those locations to form perturbed syndromes for independent BP attempts.The prior BP-SF procedure is reviewed as the basis for the GPU and windowed extensions.Source: §4 · p. 6
- Each accepted trial estimate is XORed with its trial vector, restoring consistency with the original syndrome while using the same matrix and channel LLRs.The trial vector has weight between one and min(wmax, |Φ|).Source: §4 · p. 6
- A global return selects the first converged trial; the rule relies on syndrome-consistent estimates differing from the most likely error by less than code distance implementing the same logical correction.Independent trials can execute concurrently.Source: §4 · p. 7
5 Implementations
The CUDA implementation keeps graph data and channel LLRs on the device and runs BP-SF retries speculatively. It supports ordinary BP and DMem-BP configurations.
5 Implementations
- The CUDA backend implements initial BP and speculative trials using parallel message updates and exposes a Python interface for decoder configuration and syndrome submission.Messages use single-precision floating point.Source: §5 · p. 7
- The device stores the parity-check matrix in compressed sparse row form with adjacency and edge indices, reuses message buffers, and runs flooding updates with cooperative thread groups.The initial BP iteration loop uses grid-wide barriers and tracks hard-decision changes on device.Source: §5 · p. 7
- On initial failure, CUDA blocks run independent trials with separate message states while sharing the graph and channel LLRs; an atomic success flag lets the first syndrome-valid result claim the correction.Trials stop at iteration boundaries after a result becomes available; DMem-BP trials also maintain previous output LLRs and node-specific memory strengths.Source: §5 · p. 7
6 Simulation Results
The experiments evaluate BP-SF from individual decoding calls through streaming memory, using fixed-basis and full-frame recovery protocols. They examine how retry parallelism, windowing, graph representation, and scheduling affect accuracy, latency, and correction release.
6.1 Experimental Setup
- The fixed-basis experiments and full-frame protocol have different boundary and success conditions, so decoder-accuracy comparisons are made within each protocol.Full-frame recovery checks all 24 logical X/Z labels and uses ideal X/Z extraction at both memory boundaries without destructive data readout.Source: §6.1 · p. 7, §6.4 · p. 9
6.2 Accuracy-Latency Trade off on Monolithic Decoding
- At p = 0.002 on J144,12,12K, BP-SF reaches 4.38 × 10^-6 LER per round, 83× lower than BP1000 and 2.83× lower than BP1000-OSD10; on J288 it is 18–31× higher than Relay-BP.The later latency and system-level studies focus on the 144 code, where BP-SF provides a competitive accuracy operating point.Source: §6.2 · p. 8
6.3 Temporal Scaling Using Window Decoding
- At core length 7, increasing the buffer from one to three rounds lowers LER from 2.95 × 10^-5 to 1.19 × 10^-5; a six-round buffer gives 1.20 × 10^-5 and adds roughly 9 ms to p99 release age.With a three-round buffer, a seven-round core retains most compute efficiency while releasing corrections earlier than a ten-round core.Source: §6.3 · p. 8, Table 1 · p. 8
6.2 Accuracy-Latency Trade off on Monolithic Decoding
- 13.15×: all-concurrent BP-SF reduces p99.9 call latency relative to eight-chain Relay-BP on 100,000 matched 144-code samples where every tested initial BP stage fails within 80 iterations.The comparison uses p = 0.002.Source: §6.2 · p. 8, Figure 6 · p. 9
6.3 Temporal Scaling Using Window Decoding
- Through 512 rounds, windowed BP-SF maintains effective LER near 10^-5 and 0.033–0.036 ms mean compute time per round, reaching a 17.1× speedup over monolithic decoding.At 512 rounds, 9,245 of monolithic decoding’s 9,246 failed memory experiments are attributed to non-convergence.Source: §6.3 · pp. 8–9, Figure 7 · p. 10
6.4 Full-Frame Error Correction
- For the 12-round full-frame experiment, GARI has 203,904 edges versus 419,904 for the joint matrix, a 51.4% reduction relative to the joint representation.The separate X and Z graphs contain 61,344 edges combined; joint and GARI decoding have approximately 6.85× and 3.32× as many edges, respectively.Source: §6.4 · p. 10
- With 20 retries, changing GARI from flooding to ind.128 lowers LER from 3.21 × 10^-6 to 7.95 × 10^-7; its measured LER is similar to joint D_XYZ with 100 retries.Joint D_XYZ reaches a lower LER of 2.98 × 10^-7 with 300 retries.Source: §6.4 · p. 10
- In 512-round streaming with 7/3 core/buffer geometry, GARI ind.128 had p99.9 release age 36.25 ms versus 166.29 ms for D_XYZ, with LERs of 3.24 × 10^-6 and 5.38 × 10^-6 per round.Source: Figure 8 · p. 11, §6.4 · p. 11
7 Conclusion
The paper extends BP-SF to GPU-based windowed and streaming decoding, evaluating latency, accuracy, and correction release. Results show conditional latency gains, sustained windowed performance, and improved full-frame streaming latency with a transformed graph and layered scheduling.
7 Conclusion
- On J144, 12, 12K at p = 0.002, all-concurrent BP-SF reduced mean and p99.9 latency by 6.28× and 13.15× versus eight-chain Relay-BP on 100,000 matched samples where every method’s initial BP failed within 80 iterations.These conditional timing gains do not imply uniform accuracy superiority; Relay-BP retained an accuracy advantage, particularly on J288, 12, 18K.Source: §7 · p. 12
- Through 512 rounds, 144-code fixed-basis windowed decoding maintained approximately constant per-round compute time and logical error rate, with mean compute time per round 17.1× lower than monolithic decoding.Core and buffer selection balances accuracy, decoding frequency, and correction-release delay, so compute latency alone does not capture lookahead or queuing costs.Source: §7 · p. 12
- In the 12-round 144-code full-frame experiment, GARI with independent-128 layers and 20 retries matched the measured accuracy of D_XYZ flooding with 100 retries while reducing mean and p99.9 natural-shot latency by 19.3× and 3.85×.In the tested 512-round streaming workload, its advantage also appeared as substantially less computational queuing.Source: §7 · p. 12
A.1 Full-Frame Protocol and Scoring
The full-frame protocol tracks logical-frame labels across ideal boundaries while providing only detector syndromes to the decoder. It scores both physical sectors and all logical labels, including non-convergence as failure.
A.1 Full-Frame Protocol and Scoring
- For a syndrome-consistent correction, the residual action on encoded qubits is represented up to global phase, and preserving every encoded input requires a = b = 0.The text identifies this residual action under stochastic Pauli circuit noise.Source: §A.1 · p. 13
- The circuit uses ideal initial and final X/Z stabilizer extraction around R noisy rounds, without destructive data-qubit readout; Stim annotations track logical X/Z correlations across the ideal boundaries.The decoder receives only detector syndrome, while logical labels are used for scoring and verified against the final data-qubit Pauli frame; all 24 labels of the 144 code are checked per sample.Source: §A.1 · p. 13
- Scoring checks both error sectors directly rather than extrapolating from single-basis logical error rate, and any wrong logical label or non-convergence counts as a failed experiment.For streaming, any rejected window fails the stream, and the accumulated final correction is checked by the same full-frame rule; all input rounds are retained with no monolithic rescue.Source: §A.1 · p. 13
A.2 Decoder Settings
The decoder settings combine bounded initial BP and DMem-BP retry stages with sector-specific decoding and optional GARI graph transformation. The layered schedule partitions measured checks for parallel updates and processes virtual checks in a fixed order.
A.2 Decoder Settings
- Windowed and full-frame BP-SF allow up to 80 initial min-sum BP iterations, then up to 60 DMem-BP iterations per retry, initialized from the failed attempt’s posterior memory.Fixed node-specific strengths range from −0.24 to 0.66; up to 50 oscillation-selected candidates support flip weights 1–10, with up to 100 retries per window or monolithic experiment.Source: §A.2 · p. 13
- Separate full-frame decoding estimates effective X mechanisms using D_Z, then conditions effective Z priors on the accepted estimate before decoding D_X, with shared mixed-error mechanisms reflected in conditional one-bit marginals.Treating the first estimate as certain and factorizing second-sector priors are approximations; if the first sector fails, the second uses original marginal priors, and retry budgets apply separately to failed sectors.Source: §A.2 · p. 13
- For full-frame GARI, U and V are built from the experiment’s joint detector model, and effective error variables map back to corrections with the same detector and logical effects.Flip candidates come only from original error-mechanism variables; virtual checks participate in message passing, but acceptance requires both measured X- and Z-type detector constraints.Source: §A.2 · p. 14
- The ind.128 schedule partitions measured checks into fixed, conflict-free layers of at most 128 checks, updates each layer in parallel, and reorders physical layers randomly each iteration.The two virtual-check layers then run in fixed U-then-V order; unlike original GARI, physical-check updates are not serial one check at a time.Source: §A.2 · p. 14
A.3 Sampling and Timing
The experiments use matched samples or streams with defined stopping rules and timing scopes. Full-frame accuracy, decoder timing, geometry sweeps, and streaming service traces are measured separately, with the streaming traces characterizing the tested 512-round workload.
A.3 Sampling and Timing
- Figure 6(c) timing uses 100,000 matched samples where every tested method’s native initial BP fails within 80 iterations, and measures the complete scalar call including initial BP and subsequent processing.Each sample is decoded once per configuration; sampling, scoring, construction, and warm-up are excluded, and runs use the same RTX 5060 Ti under exclusive allocations.Source: §A.3 · p. 14
- The 128-round geometry sweep used 16,384–86,016 experiments per setting until at least 100 failures; its exploratory paired 7/3 versus 10/3 comparison gave nominal exact McNemar p = 0.085.Length-sweep LER samples were matched and collected until at least 100 failures per decoder, while timings used 2,048 matched memory experiments per length.Source: §A.3 · p. 14
- The 12-round full-frame LER intervals were [5.57, 11.35] × 10^-7 for GARI ind.128 with 20 retries and [4.50, 8.98] × 10^-7 for D_XYZ flooding with 100 retries.The respective failure counts were 30 and 32; scalar timings used 524,288 matched, unfiltered samples per configuration, including failures.Source: §A.3 · p. 14
- Full-frame streaming LER estimation collected 50 failures per configuration, while 4,096 matched natural streams per setting supplied service traces for FIFO replay at 2.97-ms arrival spacing.Per-arrival processing and final flush were timed; computational waiting excludes intentional lookahead, release age includes it, and traces characterize the tested 512-round workload.Source: §A.3 · p. 14