pith. sign in

arxiv: 2605.25777 · v1 · pith:DY7ZTJJOnew · submitted 2026-05-25 · 💻 cs.IT · math.IT

Best-First Ordered Statistics Decoding of Quantum LDPC Codes

Michele Banfi , Marco Ferrari , Antonino Favano , Alberto Tarable , Luca Barletta This is my paper

Pith reviewed 2026-06-29 20:42 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords quantum LDPC codesordered statistics decodingbelief propagationbest-first searchbivariate bicycle codescircuit-level noiseerror correctionlist decoding
0
0 comments X

The pith

Best-First OSD matches BP+OSD accuracy on quantum LDPC codes while using 1/100th the candidate queries.

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

The paper introduces Best-First Ordered Statistics Decoding, which explores syndrome-consistent error candidates in decreasing order of likelihood after a fixed number of belief propagation iterations rather than waiting for BP convergence or enumerating a preset list. Monte Carlo simulations on bivariate bicycle codes under full circuit-level noise show that this yields the same logical error rates as the conventional BP+OSD pipeline. The approach is motivated by the fact that BP rarely converges reliably when every gate and measurement is noisy. If the observed query reduction holds more broadly, decoding becomes substantially cheaper for quantum error correction without sacrificing performance.

Core claim

BF-OSD traverses the space of syndrome-consistent error patterns in order of decreasing likelihood after a fixed, small number of BP iterations instead of conditioning the OSD call on BP convergence. On a family of bivariate bicycle codes under circuit-level noise, the method achieves decoding performance equivalent to the BP+OSD baseline while exploring the solution space with one-hundredth of the query budget.

What carries the argument

Best-first traversal of likelihood-ordered error candidates after a fixed number of BP iterations

If this is right

  • Decoding remains effective even when BP fails to converge, which is common under realistic circuit noise.
  • The query budget for list decoding drops by roughly two orders of magnitude while preserving accuracy.
  • The method applies directly to degenerate codes where many distinct errors produce the same syndrome.
  • A fixed BP iteration count removes the need for convergence-based early stopping logic.

Where Pith is reading between the lines

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

  • The same ordering principle could be applied to other list-decoding tasks that currently rely on exhaustive enumeration of short lists.
  • Lower per-shot query counts may allow higher clock rates or reduced hardware overhead for real-time quantum decoders.
  • If the likelihood ordering remains informative after few BP steps on additional code families, the fixed-iteration design choice becomes broadly useful.

Load-bearing premise

The performance equivalence and query reduction observed for bivariate bicycle codes under the chosen circuit-level noise model will generalize to other QLDPC codes and noise regimes without code-specific tuning.

What would settle it

Monte Carlo simulations on a different QLDPC family such as hypergraph-product codes under the same circuit-level noise model that show either a gap in logical error rate or no reduction in query count relative to BP+OSD.

Figures

Figures reproduced from arXiv: 2605.25777 by Alberto Tarable, Antonino Favano, Luca Barletta, Marco Ferrari, Michele Banfi.

Figure 1
Figure 1. Figure 1: Comparison of solution-space traversal between BF-OSD and OSD-CS [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: compares the logical error rate of BF-OSD with that of the baseline across the five BB codes, while Table I reports the corresponding values at p = 10−3 . The expected BB￾code behavior is observed: pL decreases with increasing code distance. BF-OSD tracks, and in some cases slightly improves upon the BP + OSD-CS baseline while using a comparable query budget. We further tested the same codes with a query b… view at source ↗
read the original abstract

Belief Propagation (BP) followed by Ordered Statistics Decoding (OSD) has emerged as the gold standard for decoding quantum low-density parity-check (QLDPC) codes. Recent advancements in this field have proposed new methods and algorithms to lower the complexity of this standard pipeline. Because of code degeneracy, and more in general because multiple distinct error patterns can produce the same syndrome, OSD is inherently a list-decoding technique; that is, it enumerates a set of syndrome-consistent candidates and returns the most probable one. In this work, we propose a variant of OSD, which we call Best-First OSD (BF-OSD), that explores the error-candidate space more efficiently by traversing it in order of decreasing likelihood, rather than by brute-force enumeration of a pre-selected subset. In addition, we depart from the conventional BP+OSD cascade: instead of conditioning the OSD invocation on BP convergence, we invoke OSD after a fixed, small number of BP iterations. This design choice is motivated by the full circuit-level noise regime, in which BP is particularly unreliable. Monte Carlo simulations of a family of Bivariate Bicycle (BB) codes under full circuit-level noise show that BF-OSD matches the performance of the BP+OSD baseline while exploring the solution space with 1/100th of the query budget.

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.

Referee Report

1 major / 0 minor

Summary. The paper claims that a Best-First Ordered Statistics Decoding (BF-OSD) approach, which traverses error candidates in likelihood order and invokes OSD after a fixed number of BP iterations, achieves equivalent decoding performance to the standard BP+OSD method on Bivariate Bicycle quantum LDPC codes under circuit-level noise, but with only 1/100th the OSD query budget, as demonstrated by Monte Carlo simulations.

Significance. If validated, this offers a substantial efficiency gain in decoding complexity for QLDPC codes, addressing practical challenges in quantum error correction by reducing the number of candidate evaluations needed. The empirical results on BB codes provide a useful data point for decoder design in the circuit-noise regime.

major comments (1)
  1. The abstract reports matching performance with 1/100 query budget on BB codes, but provides no error bars, no details on the exact noise model parameters, no comparison baselines beyond the standard cascade, and no statement on whether the 1/100 factor is averaged or worst-case. This weakens the support for the central empirical claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their insightful comments on our manuscript. We provide a point-by-point response to the major comment below.

read point-by-point responses

  1. Referee: The abstract reports matching performance with 1/100 query budget on BB codes, but provides no error bars, no details on the exact noise model parameters, no comparison baselines beyond the standard cascade, and no statement on whether the 1/100 factor is averaged or worst-case. This weakens the support for the central empirical claim.

    Authors: We acknowledge the abstract's brevity limits the inclusion of these specifics. The full manuscript details the exact circuit-level noise model parameters in the experimental setup. Error bars are included in the logical error rate plots from the Monte Carlo simulations. The comparison is to the standard BP+OSD cascade, which is the relevant baseline for demonstrating the query efficiency gain; additional baselines are discussed in the related work section. The 1/100 factor is the average reduction in candidate queries observed across the simulations. To better support the central claim in the abstract, we will revise it to include a short statement on the noise model and the averaged nature of the query reduction. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an algorithmic variant (BF-OSD with fixed BP iterations) whose performance is evaluated exclusively through Monte Carlo simulations on BB codes. No derivation, uniqueness theorem, or fitted parameter is invoked whose output is then relabeled as a prediction; the reported equivalence in logical error rate and query reduction is a direct empirical outcome, not a self-referential reduction. No load-bearing self-citations appear in the provided text.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the assumption that likelihood-ordered search plus fixed BP iterations yields equivalent logical error rates on the tested codes. No free parameters are explicitly fitted in the abstract; the query budget reduction is an observed outcome rather than an input. No new entities are postulated.

axioms (2)
  • domain assumption Multiple distinct error patterns can produce the same syndrome due to code degeneracy.
    Stated in the abstract as motivation for list decoding.
  • domain assumption BP is particularly unreliable under full circuit-level noise.
    Used to justify invoking OSD after a fixed number of iterations rather than on convergence.

pith-pipeline@v0.9.1-grok · 5767 in / 1420 out tokens · 22306 ms · 2026-06-29T20:42:38.435717+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 1 canonical work pages

  1. [1]

    Vasic, V

    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

  2. [2]

    Good quantum error-correcting codes exist,

    A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”Physical Review A, vol. 54, no. 2, p. 1098, 1996

    1996

  3. [3]

    Multiple-particle interference and quantum error correction,

    A. Steane, “Multiple-particle interference and quantum error correction,” Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, vol. 452, no. 1954, pp. 2551–2577, 1996

    1954

  4. [4]

    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

    2024

  5. [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, 2021

    2021

  6. [6]

    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

    2020

  7. [7]

    Efficient serial Message-Passing schedules for LDPC decoding,

    E. Sharon, S. Litsyn, and J. Goldberger, “Efficient serial Message-Passing schedules for LDPC decoding,”IEEE Transactions on Information Theory, vol. 53, no. 11, pp. 4076–4091, Nov. 2007

    2007

  8. [8]

    Topological quantum memory,

    E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,”Journal of Mathematical Physics, vol. 43, no. 9, pp. 4452– 4505, 2002

    2002

  9. [9]

    Surface codes: Towards practical large-scale quantum computation,

    A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,”Physical Review A—Atomic, Molecular, and Optical Physics, vol. 86, no. 3, p. 032324, 2012

    2012

  10. [10]

    Soft-decision decoding of linear block codes based on ordered statistics,

    M. P. C. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,”IEEE Transactions on Information Theory, vol. 41, no. 5, pp. 1379–1396, 1995

    1995

  11. [11]

    Matroids and the greedy algorithm,

    J. Edmonds, “Matroids and the greedy algorithm,”Mathematical pro- gramming, vol. 1, no. 1, pp. 127–136, 1971

    1971