Logical-Space Theory of Ordered-Statistics Decoding for Quantum LDPC Codes
Abstract
Quantum decoding succeeds when a correction matches the logical class of the error, whereas ordered-statistics decoding (OSD) searches a finite list of physical corrections. We connect these spaces through a rank-k logical-signature map Mlog:𝔽2q→𝔽2k. For fixed, error-independent orderings it yields the exact logical-signature distribution, the OSD-0 logical error rate, and the logical-class coverage of any fixed list. For minimum-cost list decoding we prove PL=Pmiss+Psel, separating absent-class from wrong-selection failures. Hypergraph-product and bivariate-bicycle codes are consistent with the coverage predictions. On the [ [144,12,12] ] gross code, 672 coverage-aware candidates outperform 899 combination-sweep candidates (paired McNemar p=0.013), while two lists with identical logical coverage give PL=11.30% and 3.78%; the signature-based coverage compression persists across 30 random column orderings. Logical coverage and within-class representative selection are therefore complementary resources that candidate count alone does not capture. The framework guides OSD list construction and compression by identifying coverage requirements and distinguishing coverage losses from failures of representative selection.
Related
- FTWeave: Composing Logical Execution, Real-Time Decoding, and Magic-State Supply in Tightly Integrated Quantum-Classical Systems
- Foundations of Many-Body Theory of Quantum Unified Statistics: Green functions and Linear Response Theory
- Work statistics of sudden quantum quenches: A random matrix theory perspective on Gaussianity and its deviations
- Logical Neural Belief Propagation for Linear-Complexity Decoding of Surface Codes
- Theory of Topologically Ordered Superfluids in 2+1 Dimensions
BibTeX
@misc{shang2026logicalspace,
title = {{Logical-Space Theory of Ordered-Statistics Decoding for Quantum LDPC Codes}},
author = {Yun Shang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24503},
eprint = {2610.24503},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24503},
}
RIS
TY - UNPB
TI - Logical-Space Theory of Ordered-Statistics Decoding for Quantum LDPC Codes
AU - Yun Shang
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24503
UR - https://arxiv.org/abs/2610.24503
AB - Quantum decoding succeeds when a correction matches the logical class of the error, whereas ordered-statistics decoding (OSD) searches a finite list of physical corrections. We connect these spaces through a rank-k logical-signature map M_log:𝔽_2^q→𝔽_2^k. For fixed, error-independent orderings it yields the exact logical-signature distribution, the OSD-0 logical error rate, and the logical-class coverage of any fixed list. For minimum-cost list decoding we prove P_L=P_miss+P_sel, separating absent-class from wrong-selection failures. Hypergraph-product and bivariate-bicycle codes are consistent with the coverage predictions. On the [ [144,12,12] ] gross code, 672 coverage-aware candidates outperform 899 combination-sweep candidates (paired McNemar p=0.013), while two lists with identical logical coverage give P_L=11.30% and 3.78%; the signature-based coverage compression persists across 30 random column orderings. Logical coverage and within-class representative selection are therefore complementary resources that candidate count alone does not capture. The framework guides OSD list construction and compression by identifying coverage requirements and distinguishing coverage losses from failures of representative selection.
ER -