CS Paper Radar

BP-based qLDPC Decoding under Long-range Correlated Noise: Trapping Configurations and Prior Mismatch

Abhinav Dangi, Avhishek Chatterjee

cs.IT quant-ph ·submitted 2026-11-07 15:19 UTC · v1

Abstract

We study the robustness of two state-of-the-art BP-based qLDPC decoders, Relay-BP and beam search, designed for independent noise when applied to spatially correlated noise with unchanged single-mechanism error probabilities. We generate correlated errors with a hidden Gaussian Markov random field, which lets us control the strength and range of the correlation while keeping every marginal error probability exact. This setting complements correlation-aware decoding: it asks how existing decoders perform when their assumed joint error model is mismatched. Across multiple tested circuits and code instances that we simulated, we observe that correlations can change logical error rates by orders of magnitude, reduce the finite-size distance advantage, and alter the relative ranking of Relay-BP, beam search, and BP-OSD. On one of the two tested circuits, Relay-BP and beam search become worse than BP-OSD, and increasing relay memory or beam width does not compensate for the degradation. Configuration analysis indicates that correlation primarily increases the probability of trapping configurations that are known to challenge these decoders; at matched error weight, correlated errors still cause decoding failures several times more often than i.i.d. errors. Finally, supplying the decoders with the marginals conditioned on the hidden field recovers most of the lost performance in the tested settings identifying prior mismatch as a major contributor to performance degradation under correlation.

Closest papers

Nearest neighbours by meaning across the whole index.

Dithered Belief Propagation for Real-Time Quantum Memory Decoding

cs.IT quant-ph ·2026-11-04 ·Zhengyu Cai, Mohamad Ali Jarkas, Bokun Zhao, Warren J. Gross
published similarity 0.60
Abstract · 7 pages, 5 figures. In the proceedings of QCE 2026

We introduce dithered belief-propagation decoding for circuit-level quantum memory to mitigate the oscillations and trapping behavior that limit standard belief-propagation (BP) decoders for qLDPC codes. Our approach combines a quantum-adapted sign-flip mechanism with chained randomized prior perturbation. Evaluated under circuit-level noise on the distance-11 rotated surface code and the distance-12 bivariate-bicycle code, the proposed dithered decoder significantly outperforms BP and BP+OSD+CS-10. The proposed decoder achieves accuracy comparable to or better than state-of-the-art Relay-BP, especially at higher physical error rates, while trading a moderate increase in additions for about 98% fewer multiplications on average and eliminating node-level RNGs. These results suggest that dithering is a promising approach toward real-time decoding of quantum memories.

0.31

Evolving Decoding Algorithms for Quantum Error Correction

cs.AI quant-phcs.MAcs.NE ·2026-11-19 ·Eduardo Dueñez, Edgar Said Hernandez Sanchez, Edgar A. Duéñez-Guzmán, Suzanne Sadedin
published similarity 0.59
Abstract · 5 main pages, 2 main figures. 15 total pages. Accepted in NeurIPS 2026 EvoRobust Workshop

Quantum computation entails robustness engineering: a noisy quantum state is measured continuously, and a classical algorithm (the decoder) must infer corrections that reliably remove the noise, fast enough to keep up. We write several published belief-propagation (BP) decoders for quantum low-density parity-check (qLDPC) codes in a Domain-Specific Language (DSL), and search over it with grammatical evolution. Written in the language, the published decoders show their parameters in plain view, allowing us to re-parameterise BP+OSD (ordered statistics decoding) and BP+LSD (localized statistics decoding) decoders with damping, before any search, making each 17.1--41.0$\times$ faster at a higher error rate, and BP+OSD-0 about 103 faster than the ldpc package's version tuned on the [[72,12,6]] bivariate-bicycle code. Evolution over the language finds decoders that improve the time-error front. One makes 23% fewer logical errors than BP+OSD-0 with damping at 0.64$\times$ its time, and decoders evolved from random code are more accurate than ldpc's tuned BP+OSD-0 at 1/31 of its time or less. Frozen at one operating point, the two fastest evolved decoders generalize well across noise levels, code sizes and round counts, staying at the time-error front. Ultimately, we demonstrate that capturing expert knowledge within a DSL creates a powerful intermediate layer---one that effectively bridges human intuition and machine-driven optimization to unlock highly efficient quantum error correction.

0.23

Fast Fault-Tolerant Decoders for Hypergraph Product and Lifted-Product Codes

cs.IT quant-ph ·2026-08-31 ·Asit Kumar Pradhan, Nithin Raveendran, David Declercq, Bane Vasić
similarity 0.58
Abstract

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.

0.31

GPU-Based Parallel BP Decoding for Quantum LDPC Memory

cs.IT quant-ph ·2026-10-09 ·Ming Wang, Yanbo Zhao, Ang Li, Frank Mueller
similarity 0.57
Abstract

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.

0.28

Belief Propagation-Informed Tesseract Decoding of Quantum LDPC Codes

cs.IT quant-ph ·2026-11-02 ·Sana Javed, Francisco Garcia-Herrero, Bane Vasić, Mark F. Flanagan
similarity 0.57
Abstract · 12 pages, 4 figures, 5 tables. Submitted to IEEE Transactions on Quantum Engineering

In quantum error correction, the decoder must estimate the errors from the measurement data accurately and fast enough to avoid a backlog. Search-based decoders such as Tesseract achieve high accuracy by finding a minimum-weight set of error events with an A* search, but their search effort grows rapidly with the physical error rate and the code size. To reduce this search effort while maintaining a logical error rate close to that of Tesseract, we propose a belief propagation (BP)-guided modification of the Tesseract decoder for quantum low-density parity-check (LDPC) codes. Damped sum-product BP is applied to the triggered detectors before the Tesseract search. If the detectors triggered by the BP hard decision match the triggered detectors, this hard decision is accepted directly, and the Tesseract search is skipped. Otherwise, the BP marginal probability estimates, weighted by a trust coefficient, modify the search priority, while the path cost keeps the channel-prior weights so that the decoding objective is unchanged. The framework also supports BP-based initialization, in which selected BP decisions form the starting point of a residual search whose signed-cost objective allows incorrect initial decisions to be removed. A node-exploration limit bounds this residual search; if the limit is reached, the decoder falls back to the BP-guided search on the original triggered detector set. The method is evaluated on the [[72,12,6]], [[90,8,10]], and [[144,12,12]] bivariate bicycle codes under circuit-level noise. With BP-based initialization and a global trust coefficient, the number of Tesseract search nodes expanded is reduced by up to more than two orders of magnitude at low physical error rates, while the logical error rate remains close to that of Tesseract.

0.22

Certified decoding of quantum LDPC codes

cs.IT quant-ph ·2026-08-26 ·Ragavi Krishnamoorthy, Florian Gerhardt, Johannes Knaute, Thomas Klir, Stefan Raimund Maschek +6 more
similarity 0.57
Abstract

Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.

0.29

Scaling Pêlagos: Multi-GPU Orchestration for Relay Belief-Propagation Decoding

cs.ET quant-ph ·2026-11-12 ·Xulong Tang, Dionysios Diamantopoulos, Tristan Müller, Apo Kayi, Nelson Mimura Gonzalez +5 more
similarity 0.55
Abstract

Fault-tolerant quantum computing requires quantum error-correction (QEC) decoders that achieve low logical error rates under real-time operating constraints. These constraints motivate heuristic decoding algorithms whose error-correction performance must be evaluated through large-scale simulation. High-throughput decoding accelerates this evaluation and the exploration of decoder parameters. Using multiple graphics processing units (GPUs) is a natural way to scale these simulations, but naively distributing syndrome batches introduces host-side preprocessing and output-collection overheads that limit scaling. To address these limitations, we extend the Pêlagos relay belief-propagation (Relay-BP) decoder with process-isolated orchestration, parallel host preprocessing, and shared-memory output. We evaluate both one-gross ($[[144,12,12]]$) and two-gross ($[[288,12,18]]$) codes in a multi-GPU environment. Specifically, for the one-gross circuit at $R=50$, eight AMD Instinct MI300X GPUs and eight AMD Instinct MI355X GPUs achieve optimized end-to-end speedups of $5.68\times$ and $6.23\times$, respectively. For the two-gross circuit, the corresponding speedups are $6.92\times$ and $7.01\times$. When throughput is calculated using GPU decoding time, the corresponding two-gross speedups are $7.58\times$ and $7.45\times$, indicating near-linear GPU scaling. We deploy Pêlagos on Lux, Oak Ridge National Laboratory's AMD Instinct MI355X-based supercomputer, as a pathfinding application for high-throughput QEC simulation. This deployment provides a concrete quantum-computing use case for the AI + HPC infrastructure supporting the Genesis Mission's scientific-discovery goals. These end-to-end measurements demonstrate a practical path to accelerating large-scale QEC simulation through efficient multi-GPU decoding.

0.16

Soft GRAND under Channel Switching and Drift

cs.IT ·2026-08-24 ·Behrooz Razeghi
published similarity 0.55
Abstract

Under channel switching or drift, the posterior used to order Guessing Random Additive Noise Decoding (GRAND) queries can differ from the matched correction posterior, increasing query rank and finite-budget error. We bound log query rank by matched posterior self-information plus positive log-posterior mismatch; exact random-subset collision probabilities bound GRAND with abandonment (GRANDAB) error. Under switching, a state-path mixture achieves vanishing error uniformly over admissible paths below the minimum constituent capacity when log path-class size is sublinear and uniform input is capacity achieving. Under drift, pilot refresh bounds mismatch and yields a continuous refresh-period minimizer. Generalized-Gaussian BPSK simulations evaluate both regimes.

0.36