Min-Sum (MS) decoding is a popular low-complexity alternative to belief propagation (BP), retaining only the minimum incoming message magnitude during check-node (CN) processing, at the cost of systematic message magnitude overestimation. The scaled MS (SMS) decoder compensates for this effect using a fixed scaling factor. We propose the syndrome adaptive gain Min-Sum (SAGMS) decoder for quantum low-density parity-check (QLDPC) codes, which adapts the message gain online based on the fraction of unsatisfied stabilizers, requiring no per-code or per-noise level optimization. We show that the scaling factor required for SMS to match belief propagation decreases with the CN degree, so any fixed scaling optimized for one degree incurs into a growing penalty as the CN degree varies. SAGMS avoids this limitation by adapting the gain during decoding. Simulations on generalized bicycle QLDPC codes demonstrate that SAGMS matches or outperforms the frame error rate (FER) of an offline optimized SMS decoder. Moreover, SAGMS approaches BP performance and, under certain conditions outperforms it while retaining MS-level complexity.
Min-Sum (MS) decoding is a popular low-complexity alternative to belief propagation (BP), retaining only the minimum incoming message magnitude during check-node (CN) processing, at the cost of systematic message magnitude overestimation. The scaled MS (SMS) decoder compensates for this effect using a fixed scaling factor. We propose the syndrome adaptive gain Min-Sum (SAGMS) decoder for quantum low-density parity-check (QLDPC) codes, which adapts the message gain online based on the fraction of unsatisfied stabilizers, requiring no per-code or per-noise level optimization. We show that the scaling factor required for SMS to match belief propagation decreases with the CN degree, so any fixed scaling optimized for one degree incurs into a growing penalty as the CN degree varies. SAGMS avoids this limitation by adapting the gain during decoding. Simulations on generalized bicycle QLDPC codes demonstrate that SAGMS matches or outperforms the frame error rate (FER) of an offline optimized SMS decoder. Moreover, SAGMS approaches BP performance and, under certain conditions outperforms it while retaining MS-level complexity.
Real-time quantum error correction requires classical decoders to process growing syndrome workloads with low and predictable latency. For quantum low-density parity-check (qLDPC) codes, iterative belief propagation (BP) repeatedly updates messages over sparse Tanner graphs, creating substantial memory-access and data-movement demands. We map normalized Min-Sum BP decoding of the [[144,12,12]] Bivariate Bicycle qLDPC code onto a DPU-based Processing-in-Memory (PIM) architecture. Within each DPU, 11 tasklets cooperatively decode one syndrome, while multiple DPUs process independent syndrome instances in parallel. Using uPIMulator and a data-qubit Pauli error model with ideal syndrome measurements, we compare throughput, per-syndrome processing time, logical error rate (LER), and single-syndrome tail latency against a 16-logical-CPU baseline. At a component-wise physical error probability of p=0.001 and one BP iteration, the projected aggregate kernel throughput of 2,560 DPUs reaches 1.071 x 10^7 decodes/s, compared with 1.22 x 10^6 decodes/s for the CPU, an 8.8x improvement. From two iterations onward, the measured LER remains below the physical error probability for every evaluated value of p. For one to five iterations, the maximum sampled serialized X+Z DPU compute latency remains below the 1 ms decoder-side reference for trapped-ion QEC, reaching approximately 0.873 ms at five iterations. These results show that near-memory processing can provide high aggregate throughput and sub-millisecond compute latency for qLDPC BP decoding under the evaluated conditions.
Many recently proposed Calderbank-Shor-Steane (CSS) quantum low-density parity-check (QLDPC) codes have sparse decoding graphs, enabling syndrome-based belief propagation (BP) decoding at low complexity. Their construction, however, often results in properties that impair BP performance, such as short cycles and degeneracy. In this work, we propose a general framework for introducing auxiliary variable nodes (AVNs) and auxiliary check nodes (ACNs) into the decoding graph of CSS codes, compatible with the standard stabilizer measurement framework. This provides an additional degree of freedom in the design of the decoding graph itself and can be used to tackle the aforementioned shortcomings. We show that recently proposed techniques, 4-cycle removal and subcode ensemble decoding, can be interpreted as instances of this framework. For 4-cycle removal, we find that the gains depend strongly on the BP iteration count and check-node message scaling. Building on this framework, we further propose a graph-derived subcode ensemble decoder and demonstrate under circuit-level noise that it substantially reduces the per-round logical error rate compared with BP on the corresponding 4-cycle-free decoding graph.
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.
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.
The min-sum (MS) and approximate-min* (a-min*) algorithms are alternatives of the belief propagation (BP) algorithm for decoding low-density parity-check (LDPC) codes. To lower the BP decoding complexity, both algorithms compute two magnitudes at each check node (CN) and pass them to the neighboring variable nodes (VNs).In this work we propose a new algorithm, ga-min*, that generalizes the MS and a-min* in terms of number of incoming messages to a CN.We analyze and demonstrate a condition to improve the performance when applying self-correction to the ga-min*. Simulations on 5G LDPC codes show that the proposed decoding algorithm yields comparable performance to the a-min* with a significant reduction in complexity, and it is robust against LLR mismatch.
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.