Adaptive decoding of quantum LDPC codes through decoder disagreement

AI summary

Overview

• Research area: Quantum error correction, specifically classical decoding of quantum low-density parity-check (qLDPC) codes using belief propagation (BP) combined with ordered-statistics decoding (OSD).
• Technical level: Intermediate. The paper assumes familiarity with syndrome extraction, BP-OSD decoding, logical error rates and AUC-style risk ranking, but its central idea is explained in plain terms.
• Scope (one sentence): The paper shows that the disagreement between two estimates produced inside a single BP-OSD pass can be used as a per-shot risk signal to decide how much expensive post-processing search each syndrome receives, and validates this on two bivariate bicycle codes, a radial lifted-product qLDPC code, and a Quantinuum H2 trapped-ion memory experiment.

What This Paper Is About

Accurate decoding of qLDPC codes usually depends on a costly post-processing search that is applied with the same fixed budget to every syndrome, even though some shots are far harder to decode than others. The authors ask whether a decoder can tell, from its own internal output, which individual shots deserve extra search. They propose using the Hamming distance between the BP hard decision and the syndrome-consistent OSD-0 solution as a risk score, and escalating only the highest-risk shots to a deeper search.

Key Contributions

1. A zero-extra-cost internal risk signal. The authors introduce the Hamming disagreement (d_{\mathrm{H}}(\hat{e}{\mathrm{BP}}, \hat{e}{\mathrm{OSD0}})) between the BP hard decision and the order-zero OSD correction as a measure of "constraint-induced reconstruction distance." Both vectors already exist after the fast decoding pass, so computing the signal costs one exclusive-or and one bit count.

2. An instance-adaptive decoding policy. Each shot takes a fast path (BP with at most 20 iterations followed by OSD-0). Shots with (d_{\mathrm{H}}) at or above a cutoff (\tau) are escalated to a truncated one-free-variable (1FV) sweep with budget (K = 1000); the rest accept the OSD-0 answer. Only the search budget changes; BP, the information set, the scoring function and the decoding objective stay fixed.

3. A matched-budget comparison against alternative routers. The disagreement router is compared, at identical escalation budgets, against routing on the BP syndrome residual (r_{\mathrm{BP}}), on syndrome weight (w_s), and at random, and against the standard BP-convergence flag used by conventional BP-OSD.

4. Cross-code and hardware validation. The mechanism is tested on a ([[144,12,12]]) and a ([[72,12,6]]) bivariate bicycle code, on an (n=90), (k=8) radial qLDPC code from a lifted-product construction, and on a full-CSS (Z)-memory experiment on the Quantinuum H2 trapped-ion processor.

Main Findings

• The benefit of deeper search is concentrated in a few shots. On the ([[144,12,12]]) code over 24 rounds with 20,000 shots per operating point at (p=0.006), (0.007) and (0.008), escalating only the top 20% of shots by disagreement recovers 91.9%, 91.5% and 84.9% of the improvement available from a full 1FV sweep (the abstract summarizes this as 85% to 92%). At 30% escalation the recovered fractions rise to 95.9%, 94.3% and 92.1%.

• The disagreement signal separates successes from failures. AUROC for OSD-0 failure is 0.958 [0.941, 0.974], 0.958 [0.951, 0.965] and 0.937 [0.930, 0.943] at the three noise rates. For the more practically relevant target, shots where OSD-0 fails but the full sweep succeeds, AUROC is 0.965, 0.957 and 0.931.

• It beats the standard BP-convergence flag by a wide margin. On the ([[144,12,12]]) benchmark BP converges on only 9.18%, 3.06% and 0.68% of shots, and the convergence flag reaches AUROC values of just 0.546, 0.516 and 0.504; routing on it would send between 90.8% and 99.3% of shots to the expensive branch. Among non-converged shots alone, (d_{\mathrm{H}}) still reaches 0.954, 0.957 and 0.936.

• The flag is more competitive but still weaker on the ([[72,12,6]]) code. There BP converges on 54.33% of shots at (p=0.006) and 29.31% at (p=0.008), and OSD-0 failures do occur among converged shots (46 and 50). The flag reaches AUROC 0.724 [0.707, 0.739] and 0.648 [0.640, 0.655], versus 0.831 [0.810, 0.852] and 0.839 [0.829, 0.850] for (d_{\mathrm{H}}), and would escalate 45.7% and 70.7% of the stream.

• A graded signal outperforms simpler syndrome statistics. The BP residual correlates strongly with (d_{\mathrm{H}}) (Spearman 0.956, 0.943 and 0.927) but is clearly less predictive: AUROC 0.842, 0.795 and 0.769, against 0.958, 0.958 and 0.937 for (d_{\mathrm{H}}) and 0.654, 0.657 and 0.659 for syndrome weight.

• Matched-budget routing matters, not just running a stronger search. At (p=0.007) and 20% escalation, disagreement routing gives a logical error rate of 0.00545, versus 0.01140 on the BP residual, 0.01385 on syndrome weight, and 0.01687 at random. Across all nine tested combinations of noise rate and budget, (d_{\mathrm{H}}) gives the lower logical error rate.

• Absolute logical error rates. Without escalation the OSD-0 baseline gives 0.00475, 0.01990 and 0.06275 at the three noise rates; the full 1FV reference gives 0.00105, 0.00410 and 0.01865, a factor of 4.52, 4.85 and 3.36. The 20% adaptive policy gives 0.00135, 0.00545 and 0.02530.

• Calibrated thresholds transfer between samples. Calibrating (\tau) on twenty seeds and applying it to twenty held-out seeds gives (\tau = 14), 21 and 32, realised escalation fractions of 20.9%, 21.7% and 20.8% (within 1.7 percentage points of the 20% target), and logical error rates of 0.00135, 0.00525 and 0.02475.

• Measured cost savings. The fast path costs 10.15 ms per shot; the truncated branch applied to every shot costs 126.2 ms at (K=500) and 131.9 ms at (K=1000); the full sweep costs 273.7 ms. Disagreement-guided routing costs 23.2, 36.3 and 49.1 ms per shot at 10%, 20% and 30% escalation, with a bootstrap interval of 32.9 to 39.9 ms at 20%. That is a factor of 3.6 saving relative to running the same (K=1000) branch on every shot, and a factor of 7.5 relative to the full sweep.

• Escalation cost comes from entering the algebraic branch, not from candidate count. At (K=1000), the fast path accounts for about 10.2 ms, the algebraic preprocessing for about 112.1 ms, and scoring the thousand candidates for about 9.6 ms; at (K=500) the scoring prefix costs only about 3.9 ms.

• A narrow headroom limits the gain, even with a good signal. On the ([[72,12,6]]) code over 12 rounds with 10,000 shots per point, the fast path gives 0.0406 and 0.1339 at (p=0.006) and (0.008), and the full sweep gives 0.0350 and 0.1101, only a factor of 1.16 and 1.22. The router still ranks well (AUROC 0.831 and 0.839) and 20% escalation gives 0.0358 and 0.1140, but there is little accuracy left to win back.

• The ordering transfers to a different code family. On the (n=90), (k=8) radial code over twelve rounds with 20,000 test shots per point, (d_{\mathrm{H}}) reaches AUROC 0.951 [0.946, 0.956] and 0.940 [0.935, 0.944] at (p=0.008) and (0.009), versus 0.832 and 0.809 for the residual and 0.707 and 0.701 for syndrome weight, reproducing the ordering (d_{\mathrm{H}} > r_{\mathrm{BP}} > w_s). At 20% escalation the policy recovers 93.9% and 86.6% of the available improvement, giving 0.02275 and 0.05390 versus 0.03290 and 0.07275 on the residual, 0.03860 and 0.07975 on syndrome weight, and 0.04525 and 0.09054 at random. The paired difference against residual routing is −0.01015 [−0.01195, −0.00880] and −0.01885 [−0.02060, −0.01690], or 203 and 377 fewer logical failures.

• Hardware confirms the signal but not a net accuracy gain. On the Quantinuum H2 processor, a ([[12,2,2]]) full-CSS (Z)-memory experiment on 22 physical qubits (12 data qubits, five (X)-check and five (Z)-check ancillas, twelve rounds) collected 300 shots. OSD-0 failed on 83 of 300 shots, a logical error rate of 0.277 [0.229, 0.330], close to the 0.266 Stim preflight. Mean (d_{\mathrm{H}}) was 1.09 on correctly decoded shots and 4.96 on failures, with AUROC 0.853 [0.804, 0.897] versus 0.886 in preflight. The full 1FV sweep rescued three failures but also turned three correct shots into failures, leaving the rate unchanged at 83 of 300, consistent with the very limited headroom of this distance-two configuration.

Methodology in Plain English

The decoder works on a detector error model derived from a circuit-level noise model. Each syndrome passes through belief propagation for at most 20 iterations, which produces posterior log-likelihood ratios and a bitwise hard decision (\hat{e}{\mathrm{BP}}). That hard decision is not required to reproduce the observed syndrome. OSD-0 then uses the same BP reliabilities to pick an information set and builds a correction algebraically that matches the syndrome exactly, (\hat{e}{\mathrm{OSD0}}).

The authors compare these two answers. If BP already produced a syndrome-consistent solution, the two coincide and the disagreement is zero. Otherwise, the number of positions where they differ measures how much BP's preferred answer had to be rewritten to fit the code's checks. A large value means BP's probabilistic view and the code's algebra conflict over many error mechanisms at once, which is where the fast path tends to fail.

Every shot is routed by that single number. Low-disagreement shots keep the OSD-0 answer. High-disagreement shots get a truncated one-free-variable sweep, which flips the first (K) free variables of the BP-derived combination-sweep ordering one at a time and scores candidates by the summed channel weight (S(x) = \sum_{i: x_i=1} \log(1/p_i)). The full 1FV sweep, which evaluates every single-free-variable perturbation (equivalent to (K = k_{\mathrm{free}}), with (k_{\mathrm{free}} = 10446) for the ([[144,12,12]]) detector error model), serves as the strong-search reference but is not an exhaustive search over physical error configurations. Escalation budgets in the main figures are imposed exactly by ranking shots on the evaluation sample; the authors also show that a threshold calibrated on separate seeds transfers to held-out data.

Why This Matters

Impact on research. The paper reframes decoding cost as something to allocate per syndrome rather than a fixed property of the pipeline, and shows that the necessary information is already present inside a single BP-OSD pass, with no ensemble, no second decoder and no trained confidence model. It also adds a sharper comparator to the reliability-estimation literature: counting how many checks BP still fails helps a great deal, and counting how many mechanisms must change before it stops failing them helps substantially more.

Real-world applications (bullets):

• Real-time decoders for fault-tolerant quantum processors, where the mean decoding time must stay below the syndrome extraction round period or the logical clock stalls.
• Hardware decoder design (FPGA or dedicated microsecond-scale decoders), where the paper's cost breakdown argues for keeping low-risk shots out of the expensive algebraic branch entirely.
• Benchmarking and validation of quantum memory experiments, where a per-shot risk score can be computed offline from the same detector stream used for decoding.
• Post-selection and abort strategies, where a per-shot risk estimate decides whether a shot is accepted rather than how deeply it is decoded.

Industry relevance. The work is relevant to groups building qLDPC-based fault tolerance and to trapped-ion and superconducting hardware teams that publish decoding latency alongside logical performance. Because the signal requires no additional decoder pass or trained model, it is a comparatively cheap addition to an existing BP-OSD stack, although the authors' timing figures are serial single-threaded measurements and reflect this particular implementation.

Future Directions

• Predicting headroom, not just risk. The authors show that a good ranking signal is not sufficient on its own: the escalated search must also be able to repair the flagged shots. The ([[72,12,6]]) code and the ([[12,2,2]]) hardware run both illustrate this, and how to estimate headroom in advance is left open. The authors describe their headroom rule as empirical, drawn from two codes and two branch depths.

• Broader code and noise-model coverage. The mechanism is demonstrated on two bivariate bicycle codes and one radial lifted-product code; extending it to other qLDPC families, larger instances and different noise models is a natural next step.

• Hardware tests with real headroom. The H2 experiment validated the risk signal but used a distance-two code with essentially no guaranteed single-error correction, so a hardware demonstration on a configuration where the strong search can actually fix failures remains to be done.

• Integration into real-time decoding pipelines. The cost measurements are serial and single-threaded, and the paper notes that in a running system the expensive branch must keep up with only a fraction (f_{\mathrm{esc}}) of the incoming syndromes. How the policy behaves under parallel and hardware-accelerated decoding is not reported.

Target Audience

This paper is most useful to quantum error-correction researchers and decoder engineers who already work with BP-OSD and qLDPC codes, to experimentalists running memory experiments who need per-shot reliability information, and to classical-hardware architects designing real-time decoders. Readers new to quantum error correction will need background in syndrome extraction and belief propagation to follow the technical sections, though the central argument is accessible.

Authors’ abstract

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.