Best-First Ordered Statistics Decoding of Quantum LDPC Codes
For quantum error correction practitioners, this work reduces the computational cost of decoding quantum LDPC codes without sacrificing accuracy.
The authors propose Best-First OSD (BF-OSD), a variant of Ordered Statistics Decoding for quantum LDPC codes that explores error candidates in decreasing likelihood order, and decouple it from BP convergence. Under circuit-level noise, BF-OSD matches BP+OSD performance while using 1/100th of the query budget.
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.