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_{\rm log}:\mathbb F_2^q\to\mathbb F_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_{\rm miss}+P_{\rm 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.
AI Summary
The paper asks how finite ordered-statistics decoding (OSD) lists cover logical equivalence classes, and how that coverage relates to decoding failure. For CSS $X$-error decoding, it constructs a surjective rank-$k$ map $M_{\rm log}=L_ZG_F$ from Gaussian-elimination free variables to logical signatures. A candidate succeeds exactly when its signature matches the error’s. For fixed, error-independent column orderings under iid bit-flip noise, Walsh inversion gives the exact signature distribution, OSD-0 logical error rate, and coverage probability of any fixed list.
Failure is partitioned exactly as $P_L=P_{\rm miss}+P_{\rm sel}$: the correct class is absent, or present but not selected by minimum cost. Signature-based list constructions are tested on hypergraph-product and bivariate-bicycle codes. For the $[[144,12,12]]$ gross code, a greedy 41-column subset covers all weight-two signatures, versus a 78-column combination-sweep prefix; a counting bound requires at least 35 columns. At $p=0.01$, a coverage-minimal 672-candidate list gives $P_L=12.42\%$, versus $13.20\%$ for 899 combination-sweep candidates on 5,000 paired shots ($p=0.013$). Lists with identical coverage but 899 and 3,082 candidates yield $11.30\%$ and $3.78\%$, demonstrating the role of within-class representatives.
Exact distributional predictions are checked against Monte Carlo, and coverage compression is tested across 30 random orderings. These are fixed-order experiments, not demonstrated BP-OSD improvements: BP-informed ordering reduces the 899-candidate baseline to $0.34\%$. Extending the averaging formulas to such orderings remains open. Exact distributions scale exponentially in $k$, and representative selection at fixed coverage and budget remains unresolved.
Little sign of AI-generated textIncrementalStrong assumptions
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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:F2q→F2k. 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.
The paper asks how finite ordered-statistics decoding (OSD) lists cover logical equivalence classes, and how that coverage relates to decoding failure. For CSS X-error decoding, it constructs a surjective rank-k map Mlog=LZGF from Gaussian-elimination free variables to logical signatures. A candidate succeeds exactly when its signature matches the error’s. For fixed, error-independent column orderings under iid bit-flip noise, Walsh inversion gives the exact signature distribution, OSD-0 logical error rate, and coverage probability of any fixed list.
Failure is partitioned exactly as PL=Pmiss+Psel: the correct class is absent, or present but not selected by minimum cost. Signature-based list constructions are tested on hypergraph-product and bivariate-bicycle codes. For the [[144,12,12]] gross code, a greedy 41-column subset covers all weight-two signatures, versus a 78-column combination-sweep prefix; a counting bound requires at least 35 columns. At p=0.01, a coverage-minimal 672-candidate list gives PL=12.42%, versus 13.20% for 899 combination-sweep candidates on 5,000 paired shots (p=0.013). Lists with identical coverage but 899 and 3,082 candidates yield 11.30% and 3.78%, demonstrating the role of within-class representatives.
Exact distributional predictions are checked against Monte Carlo, and coverage compression is tested across 30 random orderings. These are fixed-order experiments, not demonstrated BP-OSD improvements: BP-informed ordering reduces the 899-candidate baseline to 0.34%. Extending the averaging formulas to such orderings remains open. Exact distributions scale exponentially in k, and representative selection at fixed coverage and budget remains unresolved.
The measured logical error rate of a quantum low-density parity-check (QLDPC) code depends on the decoding algorithm. We develop a framework that certifies non-degenerate maximum-likelihood (ML) decoding outcomes on individual sampled shots under circuit-level noise, providing a common reference for comparing decoders and codes. Upper and lower bounds on the minimum correction cost in the true and competing logical classes establish success, failure, or an undecided outcome. Branch-and-bound search refines these intervals while retaining valid bounds under resource limits. Counting the outcomes bounds the empirical ML logical error rate, with interval width equal to the undecided fraction. Results for two bivariate bicycle codes show that best-first ordered statistics decoding (BF-OSD) tracks the non-degenerate ML benchmark closely while leaving some ML-correctable shots.
Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.
Accurate decoding of quantum low-density parity-check (qLDPC) codes often relies on expensive post-processing search, although decoding difficulty varies strongly between syndromes. We find that the benefit of deeper post-processing search is highly concentrated in a small subset of decoding instances, and that these instances can be identified directly from the decoder itself. To this end, we introduce an adaptive decoder based on belief propagation (BP) and ordered-statistics decoding (OSD), using the disagreement between the BP hard decision and the syndrome-consistent order-zero OSD solution as an internal risk signal to determine where deeper search is required. On a [[144,12,12]] bivariate bicycle code under circuit-level depolarising noise, encoding 12 logical qubits in 144 data qubits with distance 12, escalating only the highest-risk 20% of instances recovers 85% to 92% of the improvement in logical error rate available from a full one-free-variable sweep, while reducing the mean serial decoding cost by a factor of 3.6 relative to applying the same truncated search to every instance. At matched budget, disagreement-guided routing also outperforms routing based on the BP syndrome residual, syndrome weight and random selection. The same behaviour reappears on a structurally distinct radial qLDPC code obtained from a lifted-product construction, where escalating 20% of instances recovers 87% to 94% of the available gain. A Z-memory experiment on the Quantinuum H2 trapped-ion processor, implementing both X-type and Z-type checks, further shows that the signal remains predictive under device noise. These results show that decoder-internal disagreement can expose where additional decoding effort is valuable, allowing classical computation to be concentrated on the instances most likely to benefit from it.
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.
Quantum error-correcting codes protect fragile quantum information by encoding it redundantly, but identifying codes that perform well in practice with minimal overhead remains difficult due to the combinatorial search space and the high cost of logical error rate evaluation. We propose a Bayesian optimization framework to discover quantum error-correcting codes that improves data efficiency and scalability with respect to previous machine learning approaches to this task. Our main contribution is a multi-view chain-complex neural embedding that allows us to predict the logical error rate of quantum LDPC codes without performing expensive simulations. Using bivariate bicycle codes and code capacity noise as a testbed, our algorithm discovers a high-rate code [[144,36]] that achieves competitive per-qubit error rate compared to the gross code, as well as a low-error code [[144,16]] that outperforms the gross code in terms of error rate per qubit. These results highlight the ability of our pipeline to automatically discover codes balancing rate and noise suppression, while the generality of the framework enables application across diverse code families, decoders, and noise models.
The realization of quantum error correction protocols whose logical error rates are suppressed far below physical error rates relies on an intricate combination: the error-correcting code's efficiency, the syndrome extraction circuit's fault tolerance and overhead, the decoder's quality, and the device's constraints, such as physical qubit count and connectivity. This work makes two contributions towards error-corrected quantum devices. First, we introduce mirror codes, a simple yet flexible construction of LDPC stabilizer codes parameterized by a group G and two subsets of G whose total size bounds the check weight. These codes contain all abelian two-block group algebra codes, such as bivariate bicycle (BB) codes. At the same time, they are manifestly not CSS in general, thus deviating substantially from most prior constructions. Fixing a check weight of 6, we find [[60,4,10]],[[36,6,6]],[[48,8,6]], and [[85,8,9]] codes, all of which are not CSS; we also find several weight-7 codes with kd>n.
Next, we construct syndrome extraction circuits that trade overhead for provable fault tolerance. These circuits use 1-2, 3, and 6 ancillae per check, and respectively are partially fault-tolerant (FT), provably FT on weight-6 CSS codes, and provably FT on \emph{all} weight-6 stabilizer codes. Using our constructions, we perform end-to-end quantum memory experiments on several representative mirror codes under circuit-level noise. We achieve an error pseudothreshold on the order of 0.2%, approximately matching that of the [[144,12,12]] BB code under the same model. These findings position mirror codes as a versatile candidate for fault-tolerant quantum memory, especially on smaller-scale devices in the near term.