Best-First Ordered Statistics Decoding of Quantum LDPC Codes
2026-05-25 • Information Theory
Information Theory
AI summaryⓘ
The authors study a method for decoding errors in quantum error-correcting codes called Belief Propagation (BP) combined with Ordered Statistics Decoding (OSD). They propose a new version named Best-First OSD (BF-OSD) that looks for likely error candidates in a smarter order, instead of checking many possibilities randomly. They also change when OSD is applied, running it early instead of waiting for BP to fully finish, which helps in noisy environments where BP is less reliable. Their tests show BF-OSD performs just as well as the standard method but uses far fewer computations.
Quantum low-density parity-check codesBelief PropagationOrdered Statistics DecodingBest-First SearchQuantum error correctionSyndromeBivariate Bicycle codesCircuit-level noiseMonte Carlo simulationsList decoding
Authors
Michele Banfi, Marco Ferrari, Antonino Favano, Alberto Tarable, Luca Barletta
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.