arxiv: 2605.14170 · v1 · submitted 2026-05-13 · 💻 cs.IT · math.IT

Recognition: no theorem link

Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

Sheida Rabeti , Hessam Mahdavifar

Authors on Pith no claims yet

Pith reviewed 2026-05-15 01:43 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords quantum LDPC codesbelief propagation decodinglist decodingTanner graph decompositiondecoding diversitybivariate bicycle codeserror correctionparallel decoding

0 comments

The pith

MBBP-LD improves quantum LDPC decoding by running parallel belief propagation across multiple parity-check bases derived from cycle-free Tanner subtrees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD) for quantum low-density parity-check codes. It creates structured decoding diversity by building redundant parity-check matrices from cycle-free subtree decompositions of the Tanner graph and executes standard BP in parallel on those bases. This keeps linear-time complexity and avoids super-linear post-processing steps such as ordered statistics decoding. For bivariate bicycle codes [[144,12,12]] and [[288,12,18]], the method yields up to 20 percent lower error rates than BPGD and up to 30 percent lower than BP-OSD in low- and moderate-error regimes while using fewer total BP iterations. A sympathetic reader cares because the approach supplies a practical, parallelizable route to better performance without changing the underlying code or adding heavy post-processing.

Core claim

The central claim is that cycle-free subtree decompositions of the Tanner graph generate multiple consistent parity-check representations whose parallel BP decoding improves convergence and reduces logical error rates compared with single-basis BP, BP-OSD, or BPGD, all while preserving linear complexity and BP-like latency under parallel implementation.

What carries the argument

Cycle-free subtree decompositions of the Tanner graph that produce multiple redundant parity-check matrices for simultaneous BP runs.

If this is right

MBBP-LD achieves up to 20 percent lower error rates than BPGD on the tested QLDPC codes in low- and moderate-error regimes.
It achieves up to 30 percent lower error rates than BP-OSD while requiring substantially fewer total BP iterations.
The decoder maintains BP-like latency under parallel implementation even for the larger B1 code [[882,24,18≤d≤24]].
The method extends classical MBBP ideas to the quantum setting without sacrificing linear-time complexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the diversity benefit scales, the same subtree-decomposition technique could be applied to other families of quantum stabilizer codes beyond QLDPC.
Hardware realizations could exploit the inherent parallelism to lower decoding latency in fault-tolerant quantum processors.
Systematic comparison across more code parameters would clarify whether the iteration savings persist at higher code rates.

Load-bearing premise

The subtree decompositions must yield sufficiently diverse yet consistent parity-check representations that improve BP convergence without creating new inconsistencies.

What would settle it

If Monte Carlo simulations for the [[144,12,12]] bivariate bicycle code at low physical error rates show no reduction in logical error rate relative to BPGD, the performance claim is falsified.

Figures

Figures reproduced from arXiv: 2605.14170 by Hessam Mahdavifar, Sheida Rabeti.

**Figure 2.** Figure 2: Parity-check matrix H and subtree partition under permutation π = (c1, c4, c2, c3). (a) Matrix H. (b) Subtrees t1 and t2. (c) Augmented matrices H(t1) and H(t2) . Intuitively, the proposed subtree-based construction improves decoding performance by mitigating trapping-set effects [7, 18] while generating structured redundant representations. Since BP is exact on tree graphs [1], decoding over each subtree… view at source ↗

**Figure 5.** Figure 5: Decoding performance of the proposed MBBP-LD for [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗

**Figure 4.** Figure 4: Decoding performance of the proposed MBBP-LD for [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper adapts classical multiple-bases BP to quantum LDPC codes via cycle-free subtree decompositions and reports concrete error-rate gains on a few codes, but the simulation claims rest on unreported trial counts and lack error bars.

read the letter

The core move here is to take the classical MBBP idea and apply it to QLDPC codes by breaking the Tanner graph into multiple cycle-free subtrees, each giving a different parity-check matrix, then running ordinary BP on all of them in parallel. This keeps the decoder linear-time and avoids the heavier post-processing that BP-OSD uses. On the bivariate bicycle codes [[144,12,12]] and [[288,12,18]] the simulations show roughly 20% lower logical error rates than BPGD and 30% lower than BP-OSD at low-to-moderate physical error rates, plus fewer total BP iterations. The larger B1 code [[882,24,18≤d≤24]] is at least comparable to BPGD under the same parallel setup. That is the actual new piece: a structured way to generate decoding diversity that stays inside the BP framework for quantum codes. The construction itself looks workable and the reported iteration savings are a practical plus if the numbers hold. The soft spot is the simulation evidence. The abstract and stress-test note give no trial counts per data point, no sampling grid details, and no error bars. In the low-error regime those 20-30% reductions could easily sit inside binomial variance, so the headline performance claim is hard to evaluate without those numbers. The paper also does not spell out the exact subtree decomposition algorithm or how many bases were used in the plotted curves. If the full text supplies the missing statistics and the code, the gap shrinks; otherwise it stays a real limitation for anyone trying to reproduce or build on the result. The method is aimed at people already running BP-style decoders on QLDPC codes who want a modest lift without changing the complexity class. It is worth sending to peer review because the algorithmic idea is concrete, the target codes are relevant, and the claims are falsifiable once the statistical details are added. A referee would likely ask for the trial counts and a clearer description of the decomposition step, but the work is grounded enough to justify that effort.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD) for quantum LDPC codes. It generates multiple redundant parity-check representations of the Tanner graph via cycle-free subtree decompositions and runs standard BP decoding in parallel across these bases. The approach is claimed to preserve linear-time complexity while improving convergence. Simulations on the bivariate bicycle codes [[144,12,12]] and [[288,12,18]] report up to 20% lower error rates than BPGD and 30% lower than BP-OSD in low- and moderate-error regimes, with substantially fewer total BP iterations; comparable or better performance is reported for the larger B1 code [[882,24,18≤d≤24]].

Significance. If the reported error-rate reductions are statistically robust, the work would constitute a useful practical advance for QLDPC decoding. It introduces structured diversity without super-linear post-processing or loss of BP's linear complexity, and the parallelizable nature could translate to lower latency under hardware implementation. This is relevant for scaling fault-tolerant quantum computation with QLDPC codes.

major comments (2)

[Abstract] Abstract and simulation results: The central performance claims (20% error-rate reduction versus BPGD and 30% versus BP-OSD for the [[144,12,12]] and [[288,12,18]] codes) are presented without any information on the number of Monte Carlo trials per data point, the physical-error-rate sampling grid, or the method used to compute error bars. In the low-error regime where failure probabilities are small, these omissions make it impossible to determine whether the reported gains exceed binomial sampling variance.
[Method] Method description (cycle-free subtree decompositions): The precise algorithm for constructing the multiple bases, including the number of bases generated and the exact decomposition procedure that guarantees cycle-free subtrees while preserving consistency of the parity-check equations, is not specified. This detail is load-bearing for the claim that the representations produce sufficiently diverse yet consistent inputs that improve BP convergence without introducing new inconsistencies.

minor comments (1)

[Abstract] The abstract states that MBBP-LD requires 'substantially fewer total BP iterations' but provides no quantitative comparison (e.g., average iterations per frame or total iteration count under parallel execution) against BPGD and BP-OSD.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments highlight important aspects of statistical robustness and algorithmic clarity that we address below. We have revised the manuscript to incorporate additional details on simulations and the base-construction procedure.

read point-by-point responses

Referee: [Abstract] Abstract and simulation results: The central performance claims (20% error-rate reduction versus BPGD and 30% versus BP-OSD for the [[144,12,12]] and [[288,12,18]] codes) are presented without any information on the number of Monte Carlo trials per data point, the physical-error-rate sampling grid, or the method used to compute error bars. In the low-error regime where failure probabilities are small, these omissions make it impossible to determine whether the reported gains exceed binomial sampling variance.

Authors: We agree that explicit reporting of Monte Carlo parameters is required to establish statistical significance. In the revised manuscript we have added a dedicated simulation-details subsection stating that each data point is obtained from at least 10^7 independent trials (increased to 5×10^7 for physical error rates below 0.01), that the sampling grid consists of 20 logarithmically spaced points between 0.001 and 0.12, and that error bars are computed via the Clopper-Pearson binomial confidence interval at 95 %. With these sample sizes the observed 20–30 % reductions lie well outside the sampling variance for the reported operating points. revision: yes
Referee: [Method] Method description (cycle-free subtree decompositions): The precise algorithm for constructing the multiple bases, including the number of bases generated and the exact decomposition procedure that guarantees cycle-free subtrees while preserving consistency of the parity-check equations, is not specified. This detail is load-bearing for the claim that the representations produce sufficiently diverse yet consistent inputs that improve BP convergence without introducing new inconsistencies.

Authors: Section III-B already outlines the high-level construction, but we acknowledge that the exact algorithmic steps and parameter choices were insufficiently explicit. In the revision we have inserted a new Algorithm 1 box together with a short paragraph that (i) fixes the number of bases to K=4 for all reported experiments, (ii) describes the iterative spanning-tree selection via a modified Kruskal procedure that enforces acyclicity on each subtree, and (iii) proves that the resulting parity-check matrices remain linearly equivalent to the original H by construction (each new row is an integer linear combination of the original rows). This guarantees consistency while introducing the desired diversity. revision: yes

Circularity Check

0 steps flagged

No significant circularity: algorithmic decoder extension validated by independent Monte Carlo simulations

full rationale

The paper defines MBBP-LD as an explicit algorithmic procedure: construct multiple redundant parity-check matrices via cycle-free subtree decompositions of the Tanner graph, then run standard BP in parallel across them. This construction is self-contained and does not reduce to any fitted parameter or prior result by definition. The headline performance numbers (20% and 30% error-rate reductions for the [[144,12,12]] and [[288,12,18]] codes) are obtained from separate Monte Carlo trials, not from any equation inside the decoder. No self-citation is invoked as a uniqueness theorem or to justify the core construction; the classical MBBP reference is used only for context. Because the claimed improvements rest on external simulation data rather than on any internal fit or renaming, the derivation chain contains no circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that cycle-free subtree decompositions of the Tanner graph yield useful redundant parity-check bases for BP without introducing inconsistencies.

axioms (1)

domain assumption Cycle-free subtree decompositions of the Tanner graph produce multiple consistent yet diverse parity-check representations suitable for parallel BP decoding.
Invoked in the key idea of generating structured decoding diversity.

pith-pipeline@v0.9.0 · 5567 in / 1309 out tokens · 34481 ms · 2026-05-15T01:43:21.738775+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Low-density parity-check codes,

R. Gallager, “Low-density parity-check codes,”IRE Transactions on information theory, vol. 8, no. 1, pp. 21–28, 1962

work page 1962
[2]

Fifteen years of quantum LDPC coding and improved decoding strategies,

Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, “Fifteen years of quantum LDPC coding and improved decoding strategies,”iEEE Access, vol. 3, pp. 2492–2519, 2015

work page 2015
[3]

Quantum low-density parity- check codes,

N. P. Breuckmann and J. N. Eberhardt, “Quantum low-density parity- check codes,”PRX quantum, vol. 2, no. 4, p. 040101, 2021

work page 2021
[4]

Quantum low-density parity-check codes,

B. Vasic, V . Savin, M. Pacenti, S. Borah, and N. Raveendran, “Quantum low-density parity-check codes,”arXiv preprint arXiv:2510.14090, 2025

work page arXiv 2025
[5]

Degenerate quantum LDPC codes with good finite length performance,

P. Panteleev and G. Kalachev, “Degenerate quantum LDPC codes with good finite length performance,”Quantum, vol. 5, p. 585, Nov. 2021

work page 2021
[6]

Layered decoding of quantum LDPC codes,

J. Du Crest, F. Garcia-Herrero, M. Mhalla, V . Savin, and J. Valls, “Layered decoding of quantum LDPC codes,” in2023 12th International Symposium on Topics in Coding (ISTC). IEEE, 2023, pp. 1–5

work page 2023
[7]

Trapping sets of quantum LDPC codes,

N. Raveendran and B. Vasi ´c, “Trapping sets of quantum LDPC codes,” Quantum, vol. 5, p. 562, 2021

work page 2021
[8]

Enhanced min-sum decoding of quantum codes using previous iteration dynamics,

D. Chytas, N. Raveendran, and B. Vasic, “Enhanced min-sum decoding of quantum codes using previous iteration dynamics,”arXiv preprint arXiv:2501.05021, 2025

work page arXiv 2025
[9]

Stabilizer inactivation for message- passing decoding of quantum LDPC codes,

J. Du Crest, M. Mhalla, and V . Savin, “Stabilizer inactivation for message- passing decoding of quantum LDPC codes,” in2022 IEEE Information Theory Workshop (ITW). IEEE, 2022, pp. 488–493

work page 2022
[10]

Belief propagation decoding of quantum LDPC codes with guided decimation,

H. Yao, W. A. Laban, C. Häger, A. G. i Amat, and H. D. Pfister, “Belief propagation decoding of quantum LDPC codes with guided decimation,” in2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024, pp. 2478–2483

work page 2024
[11]

Ambiguity clustering: an accurate and efficient decoder for QLDPC codes,

S. Wolanski and B. Barber, “Ambiguity clustering: an accurate and efficient decoder for QLDPC codes,”arXiv preprint arXiv:2406.14527, 2024

work page arXiv 2024
[12]

Localized statistics decoding for quantum low-density parity- check codes,

T. Hillmann, L. Berent, A. O. Quintavalle, J. Eisert, R. Wille, and J. Roffe, “Localized statistics decoding for quantum low-density parity- check codes,”Nature Communications, vol. 16, no. 1, p. 8214, 2025

work page 2025
[13]

An almost-linear time decoding algorithm for quan- tum ldpc codes under circuit-level noise,

A. deMarti iOlius, I. Etxezarreta Martinez, J. Roffe, and J. Etx- ezarreta Martinez, “An almost-linear time decoding algorithm for quan- tum ldpc codes under circuit-level noise,”arXiv e-prints, pp. arXiv–2409, 2024

work page 2024
[14]

Multiple- bases belief-propagation decoding of high-density cyclic codes,

T. Hehn, J. B. Huber, O. Milenkovic, and S. Laendner, “Multiple- bases belief-propagation decoding of high-density cyclic codes,”IEEE transactions on communications, vol. 58, no. 1, pp. 1–8, 2010

work page 2010
[15]

Multiple-bases belief-propagation for decoding of short block codes,

T. Hehn, J. B. Huber, S. Laendner, and O. Milenkovic, “Multiple-bases belief-propagation for decoding of short block codes,” in2007 IEEE International Symposium on Information Theory. IEEE, 2007, pp. 311– 315

work page 2007
[16]

Augmented decoders for LDPC codes,

A. R. Rigby, J. C. Olivier, H. C. Myburgh, C. Xiao, and B. P. Salmon, “Augmented decoders for LDPC codes,”EURASIP Journal on Wireless Communications and Networking, vol. 2018, no. 1, p. 189, 2018

work page 2018
[17]

Modified belief propagation decoders for quantum low-density parity-check codes,

A. Rigby, J. Olivier, and P. Jarvis, “Modified belief propagation decoders for quantum low-density parity-check codes,”Physical Review A, vol. 100, no. 1, p. 012330, 2019

work page 2019
[18]

Finite-length analysis of low-density parity-check codes on the binary erasure channel,

C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-length analysis of low-density parity-check codes on the binary erasure channel,”IEEE Transactions on Information theory, vol. 48, no. 6, pp. 1570–1579, 2002

work page 2002
[19]

Bounds and new constructions for girth-constrained regular bipartite graphs,

S. Rabeti, M. Moradi, and H. Mahdavifar, “Bounds and new constructions for girth-constrained regular bipartite graphs,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

work page 2025
[20]

High-threshold and low-overhead fault-tolerant quantum memory,

S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, “High-threshold and low-overhead fault-tolerant quantum memory,”Nature, vol. 627, no. 8005, pp. 778–782, 2024

work page 2024
[21]

Sequential BP- based decoding of QLDPC codes,

M. Moradi, S. Habib, V . Nourozi, and D. G. Mitchell, “Sequential BP- based decoding of QLDPC codes,”arXiv preprint arXiv:2602.13420, 2026

work page arXiv 2026
[22]

Decoding across the quantum low-density parity-check code landscape,

J. Roffe, D. R. White, S. Burton, and E. Campbell, “Decoding across the quantum low-density parity-check code landscape,”Physical Review Research, vol. 2, no. 4, p. 043423, 2020

work page 2020
[23]

LDPC: Python tools for low density parity check codes,

J. Roffe, “LDPC: Python tools for low density parity check codes,”PyPI https://pypi. org/project/ldpc, 2022

work page 2022