Best-First Ordered Statistics Decoding of Quantum LDPC Codes

摘要

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.

核心问题与主要方法

核心问题

Reduce the complexity of BP+OSD decoding for quantum LDPC codes while preserving decoding performance under degeneracy and circuit-level noise

场景：Quantum LDPC decoding for CSS-based BB codes under full circuit-level noise, using spatio-temporal decoding matrices and short BP warm-up followed by OSD

主要方法

Construct an OSD-0 baseline from BP soft outputs, using confidence-based column ordering plus a syndrome-decoding pre-flip for bits with negative LLR. Represent all syndrome-consistent candidates as an affine coset E_base + ker(H_dec), with null-space generators read from Gaussian elimination. Search XOR combinations of null-space generators using a best-first priority queue ordered by negative log-likelihood cost. Avoid duplicate generator combinations by enforcing an increasing-index expansion rule. Always invoke OSD after a small fixed number of sequential BP iterations rather than conditioning OSD on BP convergence.

关键贡献与后续阅读

关键贡献

Introduces BF-OSD as a cost-ordered, best-first alternative to OSD-w and OSD-CS fixed-region enumeration for QLDPC decoding. Reframes OSD exploration as traversal of the affine coset of syndrome-consistent errors using null-space generators of the decoding matrix. Provides an anytime decoding procedure where every candidate is syndrome-valid and the best retained candidate can only improve as the query budget increases. Adapts confidence-based OSD column ordering to quantum syndrome decoding through a pre-flip/update of the syndrome for negative-LLR hard decisions. Combines short sequential BP warm-up with unconditional BF-OSD invocation for full circuit-level noise, where BP convergence is slow and unreliable. Reports Monte Carlo evidence on BB codes under full circuit-level noise that BF-OSD can match or slightly improve BP+OSD-CS performance at comparable or much smaller query budgets.

研究启发

What are the exact BB-code parameters and logical error-rate confidence intervals in Table I/Figure 2? How sensitive is the 1/100 query-budget claim to physical error rate, code distance, and the choice of Q? Does BF-OSD retain the same advantage under min-sum or other hardware-friendly BP approximations? What memory overhead does the priority queue introduce relative to OSD-CS in large decoding matrices?

限制与不确定性

Evidence appears simulation-focused on a BB-code family, so generality beyond that setting is uncertain. Performance and value may depend on query-budget choices and implementation details of ordering/search. No full-paper reread was used, so ratings rely on the provided relevance and structure extraction.

参考文献

11 条

[1] S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder (2024) High-threshold and low-overhead fault-tolerant quantum memory . Nature 627 ( 8005 ), pp. 778–782 . Cited by: §I , §II , §II , §II , § III-C , Figure 2 , § VI-A , TABLE I , TABLE I , §VII .
[2] A. R. Calderbank and P. W. Shor (1996) Good quantum error-correcting codes exist . Physical Review A 54 ( 2 ), pp. 1098 . Cited by: §I .
[3] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill (2002) Topological quantum memory . Journal of Mathematical Physics 43 ( 9 ), pp. 4452–4505 . Cited by: §II .
[4] J. Edmonds (1971) Matroids and the greedy algorithm . Mathematical programming 1 ( 1 ), pp. 127–136 . Cited by: §VII .
[5] M. P. C. Fossorier and S. Lin (1995) Soft-decision decoding of linear block codes based on ordered statistics . IEEE Transactions on Information Theory 41 ( 5 ), pp. 1379–1396 . Cited by: § III-B , § IV-B .
[6] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland (2012) Surface codes: towards practical large-scale quantum computation . Physical Review A—Atomic, Molecular, and Optical Physics 86 ( 3 ), pp. 032324 . Cited by: §II .
[7] P. Panteleev and G. Kalachev (2021) Degenerate quantum LDPC codes with good finite length performance . Quantum 5 , pp. 585 . Cited by: §I .
[8] J. Roffe, D. R. White, S. Burton, and E. Campbell (2020) Decoding across the quantum low-density parity-check code landscape . Physical Review Research 2 ( 4 ), pp. 043423 . Cited by: §I , § III-B , § III-C , §III , § IV-A .
[9] E. Sharon, S. Litsyn, and J. Goldberger (2007-Nov.) Efficient serial Message-Passing schedules for LDPC decoding . IEEE Transactions on Information Theory 53 ( 11 ), pp. 4076–4091 . Cited by: §I .
[10] A. Steane (1996) Multiple-particle interference and quantum error correction . Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452 ( 1954 ), pp. 2551–2577 . Cited by: §I .
[11] B. Vasic, V. Savin, M. Pacenti, S. Borah, and N. Raveendran (2025) Quantum low-density parity-check codes . arXiv preprint arXiv:2510.14090 . Cited by: §I .