QEC decoders head to head: MWPM, correlated MWPM, BP, BP+OSD and exact minimum-weight decoding on surface, repetition and bivariate-bicycle codes
Abstract. Experiment 11 pitted generic ML against minimum-weight perfect matching (MWPM). This experiment compares the real decoders with each other, on identical shots. The decoders are PyMatching 2.4 MWPM (plain and with enable_correlations), belief propagation (min-sum and product-sum), BP+OSD (OSD-0 and OSD-CS order 7, Roffe's ldpc 2.4.1) and an exact minimum-weight reference solved as an integer linear programme (HiGHS). They run on (a) Stim circuit-level memory experiments of the rotated surface code (d = 3, 5, 7; up to 336 detectors × 5 471 error mechanisms) and the repetition code (d = 3–9), and (b) three bivariate-bicycle (BB) qLDPC codes, [[72,12,6]], [[108,8,10]] and [[144,12,12]], under code-capacity noise. We use 3 noise seeds, Wilson intervals and paired McNemar tests. On the surface code at d ≥ 5, correlated MWPM and BP+OSD-CS are statistically tied at all 12 grid points (McNemar p ≥ 0.17), and both beat plain MWPM, correlated MWPM by up to 1.85× (d = 7, p = 0.005: 5.45·10⁻³ vs 1.01·10⁻²). At p = 0.005, BP+OSD-CS costs 3.9 ms (d = 5) and 50 ms (d = 7) per shot, against 5.7 µs and 17 µs for correlated matching: 690–2 900× slower for no measurable gain. BP alone has no threshold on the surface code: its LER grows with d at every p (d = 7, p = 0.001: 4.5·10⁻² vs MWPM 1.0·10⁻⁴), and its convergence rate falls from 96.5 % to 0.1 %. BP+OSD is also fragile at low p. With ldpc's sinter default (min-sum scaling 0.625) it is 3.5× worse than MWPM at d = 3, p = 0.001. On some shots BP converges to a syndrome-valid correction about e²⁷ times less likely than the optimum, so OSD never runs. A serial schedule fixes this. Unscaled min-sum fixes it too, but on [[144,12,12]] it raises the LER from 0.067 to 0.83. On the BB codes MWPM does not apply (PyMatching refuses weight-3 columns). There BP+OSD-CS wins at every p ≤ 0.05, by 2–6.5× over OSD-0 and BP on [[108,8,10]] and [[144,12,12]], and by only 1.0–1.3× on [[72,12,6]]. Yet on [[72,12,6]] the exact minimum-weight decoder still beats it at p = 0.02 (0.015 vs 0.024, McNemar p = 0.005). The ILP stays tractable up to d = 7 (0.41 s per non-trivial syndrome) and is 10⁴–10⁵× slower than matching. Adjacent-d crossings of the circuit-level surface-code curves: MWPM 0.63 % / 0.75 %, correlated MWPM 0.77 % / 0.88 %, BP+OSD-CS 0.63 % / 0.70 % (d = 3/5 and 5/7, coarse grid).
Google Quantum AI's surface-code memory experiments (Nature 614, 676 (2023), arXiv:2207.06431; below threshold in Nature 638, 920 (2025), arXiv:2408.13687) report matching-based decoders (plain, correlated, ensembled) alongside tensor-network and neural decoders. Minimum-weight perfect matching (MWPM; Dennis, Kitaev, Landahl & Preskill, J. Math. Phys. 43, 4452 (2002); Fowler et al., PRA 86, 032324 (2012)) remains the reference. PyMatching 2's sparse blossom (Higgott & Gidney, arXiv:2303.15933) runs it in microseconds per shot on circuit-level noise. MWPM needs a graph: every error mechanism must flip at most two detectors. Circuit-level noise violates this (a Y error on a data qubit flips an X-type and a Z-type detector pair); PyMatching decomposes such hyperedges into edges and loses the correlation, and its enable_correlations option re-weights the halves after a first pass (in the spirit of Fowler, arXiv:1310.0863). Quantum LDPC codes such as the bivariate-bicycle (BB) codes (Bravyi et al., Nature 627, 778 (2024), arXiv:2308.07915) have every qubit in three checks of each type, so MWPM does not apply at all; their standard decoder is belief propagation followed by ordered-statistics decoding, BP+OSD (Panteleev & Kalachev, Quantum 5, 585 (2021), arXiv:1904.02703; Roffe et al., PRR 2, 043423 (2020), arXiv:2005.07016). The review by iOlius et al. (arXiv:2307.14989) surveys these families.
Experiment 11 in this repository compared MWPM with generic tabular ML and found that ML never sees the threshold. What this repository did not have is the comparison practitioners actually face: the real decoders against each other, on identical shots, with confidence intervals, a time per shot, and an exact reference that says how far each heuristic is from the optimum of the problem it claims to solve. Published comparisons usually report one decoder per code family (MWPM for surface codes, BP+OSD for qLDPC codes) and rarely report an exact minimum-weight reference or the BP flavour a result depends on.
Circuit-level memory. Stim generates the rotated surface code (surface_code:rotated_memory_z) and the repetition code (repetition_code:memory) with rounds = d and uniform noise p (after every Clifford, on data qubits before every round, on measurement and on reset). Its detector error model (DEM, decompose_errors=False) is turned into a decoding problem: H ∈ {0,1}^{m×n} (detectors × error mechanisms, identical columns merged), L ∈ {0,1}^{1×n} (observable), priors p_j. A shot gives a syndrome s = He and a true flip o = Le (mod 2). A decoder returns a correction ê with Hê = s (ideally) and predicts Lê; the shot fails if Lê ≠ o.
Code capacity on a CSS code. For a BB code with checks H_X = [A | B], H_Z = [Bᵀ | Aᵀ], A = x³ + y + y², B = y³ + x + x² (x = S_l ⊗ I_6, y = I_l ⊗ S_6, S = cyclic shift; l = 6, 9, 12 give [[72,12,6]], [[108,8,10]], [[144,12,12]]), independent X and Z flips of probability p hit every qubit. X errors are decoded from s_X = H_Z e_X and fail if L_Z(e_X + ê_X) ≠ 0 for any of the k Z-logicals; Z errors likewise with H_X, L_X. A shot fails if either sector fails (block error of all k logical qubits). H_X H_Zᵀ = AB + BA = 0 because A and B commute.
Minimum-weight decoding (the exact reference).
min Σ_j w_j e_j s.t. H e − 2z = s, e ∈ {0,1}^n, z ∈ ℤ^m_{≥0}, w_j = ln((1 − p_j)/p_j)
solved by HiGHS (scipy.optimize.milp, relative MIP gap 0). This is the most likely error, not the most likely logical coset (degenerate maximum likelihood, #P-hard in general; Iyer & Poulin, IEEE TIT 61, 5209 (2015)), so a heuristic can beat it on logical error rate and that is not a contradiction.
| arm | what it is | applies to |
|---|---|---|
mwpm |
PyMatching 2.4 on the matching graph of the decomposed DEM, decode_batch |
surface, repetition |
mwpm_corr |
same with enable_correlations=True (two-pass correlated matching) |
surface, repetition |
bp_ms |
BP min-sum, scaling 0.625, parallel schedule, ≤ 50 iterations; hard decision whether or not it converged | all |
bp_ps |
BP product-sum, parallel, ≤ 50 iterations | all |
bposd0 |
bp_ms + OSD-0 when BP does not converge |
all |
bposd_cs |
bp_ms + OSD-CS of order 7 (combination sweep of Roffe et al. 2020: all weight-1 flips of the non-pivot bits + weight-2 flips among the first 7) |
all |
ilp |
exact minimum-weight decoding (above) | surface d = 3 and 5, BB [[72,12,6]] |
none |
predict "no flip": LER = raw logical parity of the error | all |
random |
uniformly random syndrome-consistent correction (particular solution + uniform kernel element, GF(2) elimination), seeded per instance | all |
BP and OSD come from Roffe's ldpc 2.4.1 (C++ core), which installed from a prebuilt arm64 / Python 3.13 wheel via uv add ldpc, so no BP+OSD was re-implemented here. The three BP-based arms bp_ms, bposd0, bposd_cs are scored from one BpOsdDecoder(osd_method="osd_cs") call per shot (its BP hard decision, its OSD-0 solution and its OSD-CS solution), so they share the BP run. BP and BP+OSD for the surface code run on the same undecomposed DEM matrix as the ILP (the stimbposd construction, O. Higgott), so every decoder sees the same shots and the same noise model; MWPM sees the decomposed version of that DEM. The min-sum scaling 0.625 is ldpc's sinter default; §5.8 varies it.
Shots and stopping rule. Per grid point, 3 noise seeds are sampled and interleaved (shot i belongs to seed i mod 3), 20 000 shots in total. none, mwpm and mwpm_corr decode all 20 000; random the first 5 000. The per-shot decoders decode a prefix of the same stream and stop at ≥ 100 failures of their best member or at a deterministic shot cap (surface: 20 000 / 5 000 / 1 000 shots at d = 3 / 5 / 7; repetition and BB: 20 000; ILP: 2 000 shots at surface d = 3 and on [[72,12,6]], 500 at surface d = 5). A 300 s safety budget exists but never bound: every stop reason in results.json is failures or cap. So every point has either ≥ 100 failures or the stated cap. Because decoders are deterministic, repeated syndromes are decoded once (a cache); timing is measured separately.
Metrics. LER per shot with Wilson 95 % intervals on the pooled shots; the mean and standard deviation of the three per-seed LERs; BP convergence rate; decoding time per shot from a separate timing pass (each decoder alone, no cache, same first ≤ 300 shots after a 20-shot warm-up, single thread; MWPM through decode_batch over all shots and also per call); gap to the ILP on the common prefix of shots (fraction of shots whose correction is heavier than the optimum, lighter than the optimum (a sanity check, must be 0), invalid (syndrome not reproduced), predicted flip different from the ILP's, and the paired LER difference); paired comparisons between decoders on their common prefix of identical shots (discordant counts, LER difference with a 95 % normal-approximation CI, exact McNemar binomial p-value); adjacent-size crossings of the LER(p) curves by log-log interpolation, with a parametric-bootstrap 95 % interval (failures redrawn binomially, 1 000 replicates).
Side studies. (i) BP iteration budget 10/30/50/100 for BP+OSD on identical shots; (ii) BP flavour inside BP+OSD-CS (min-sum 0.625, min-sum 1.0, product-sum, serial min-sum 0.625); (iii) ILP solve time per non-trivial syndrome versus instance size (surface d = 3, 5, 7; BB 72, 108, 144); (iv) the code distance of the BB codes by ILP (min |x| s.t. H_Z x = 0, L_Z[j]·x = 1).
Relation to qcore. qcore's IR has no DETECTOR / OBSERVABLE_INCLUDE annotations, no detector-error-model export and no decoders, so this experiment calls Stim, PyMatching, ldpc and HiGHS directly (contract rule 3). make_circuit and sample_detectors are copied from experiment 11, not imported.
| item | value |
|---|---|
| surface code (Z memory, rounds = d) | d = 3: 24 detectors, 219 DEM mechanisms (113 hyperedges), 78 matching-graph edges; d = 5: 120 / 1 677 (1 101) / 502; d = 7: 336 / 5 471 (3 793) / 1 558 |
| repetition code (rounds = d) | d = 3, 5, 7, 9: 8 / 24 / 48 / 80 detectors, 21 / 65 / 133 / 225 mechanisms, no hyperedges |
| circuit-level p | 0.001, 0.002, 0.003, 0.005, 0.007, 0.01 |
| BB codes (code capacity) | [[72,12,6]] (l = 6), [[108,8,10]] (l = 9), [[144,12,12]] (l = 12); m = 6; 36 / 54 / 72 checks per type, weight 6, qubit degree 3 |
| code-capacity p (per qubit, per Pauli type) | 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.08, 0.10, 0.12 |
| shots per point | 20 000 sampled (3 seeds × 6 667 interleaved); per-shot decoders stop at 100 failures or the cap in §3 |
| BP budget | 50 iterations for every BP-based arm (bp_ms, bp_ps, bposd0, bposd_cs); ablation 10/30/50/100 in §5.8 |
| OSD | OSD-0 and OSD-CS order 7 |
| ILP | scipy.optimize.milp (HiGHS), mip_rel_gap = 0, 10 s time limit per solve (never hit) |
| seed | 0 (--seed); per-instance seeds = CRC32 of (seed, family, d, p, noise-seed index) |
| hardware | Apple Silicon laptop (10 cores), Python 3.13, single process; load average 17–56 from three sibling experiments during the run |
| wall-clock, full run | 911.6 s (15.2 min): surface 691 s (of which the d = 5 ILP arm ≈ 164 s), repetition 20 s, BB 84 s, BP-flavour study 55 s, distance ILPs 32 s, iteration ablation 22 s, ILP size probe 6 s |
wall-clock, --quick |
15–25 s depending on machine load (surface d = 3, 5 and repetition d = 3, 5 at p = 0.003, 0.01; [[72,12,6]], [[144,12,12]] at p = 0.03, 0.08; 2 000 shots) |
| packages | stim 1.16.0, pymatching 2.4.0, ldpc 2.4.1 (prebuilt arm64 wheel), scipy 1.18.1 / HiGHS |
All numbers below are copied from results/results.json (also flattened in results/ler_table.csv). The LER notation 1.33e-2 [1.09, 1.61] means 1.33·10⁻² with a Wilson 95 % interval [1.09, 1.61]·10⁻². 0 [≤ x] means no failures, with x the 95 % upper bound.
| d | p | MWPM | correlated MWPM | BP+OSD-CS7 | BP+OSD-0 | exact MW (ILP) |
|---|---|---|---|---|---|---|
| 3 | 0.001 | 5.50e-4 [3.07, 9.85] | 9.00e-4 [5.69, 14.22] | 1.95e-3 [1.43, 2.66] | 2.60e-3 [1.98, 3.41] | 5.00e-4 [0.88, 28.27] |
| 3 | 0.002 | 3.25e-3 [2.55, 4.14] | 3.20e-3 [2.51, 4.08] | 2.50e-3 [1.90, 3.29] | 3.90e-3 [3.13, 4.86] | 3.50e-3 [1.70, 7.21] |
| 3 | 0.003 | 5.70e-3 [4.75, 6.84] | 6.40e-3 [5.39, 7.60] | 4.75e-3 [3.89, 5.80] | 6.60e-3 [5.57, 7.82] | 6.50e-3 [3.80, 11.09] |
| 3 | 0.005 | 1.79e-2 [1.61, 1.98] | 1.70e-2 [1.53, 1.89] | 1.33e-2 [1.09, 1.61] | 1.52e-2 [1.27, 1.83] | 1.55e-2 [1.09, 2.19] |
| 3 | 0.007 | 3.18e-2 [2.95, 3.43] | 3.23e-2 [3.00, 3.49] | 2.66e-2 [2.19, 3.22] | 3.06e-2 [2.55, 3.65] | 2.60e-2 [1.99, 3.39] |
| 3 | 0.01 | 5.87e-2 [5.55, 6.20] | 5.76e-2 [5.45, 6.09] | 5.15e-2 [4.26, 6.23] | 5.52e-2 [4.58, 6.62] | 4.95e-2 [4.08, 5.99] |
| 5 | 0.001 | 1.50e-4 [0.51, 4.41] | 1.00e-4 [0.27, 3.65] | 0 [≤ 7.7e-04] | 0 [≤ 7.7e-04] | 0 [≤ 7.6e-03] |
| 5 | 0.002 | 1.05e-3 [0.69, 1.60] | 8.50e-4 [5.31, 13.61] | 1.20e-3 [0.55, 2.62] | 1.40e-3 [0.68, 2.89] | 0 [≤ 7.6e-03] |
| 5 | 0.003 | 3.70e-3 [2.95, 4.64] | 1.95e-3 [1.43, 2.66] | 1.80e-3 [0.95, 3.42] | 4.20e-3 [2.75, 6.41] | 2.00e-3 [0.35, 11.24] |
| 5 | 0.005 | 1.32e-2 [1.18, 1.49] | 1.08e-2 [0.95, 1.24] | 8.80e-3 [6.56, 11.79] | 1.58e-2 [1.27, 1.96] | 4.00e-3 [1.10, 14.47] |
| 5 | 0.007 | 3.65e-2 [3.40, 3.92] | 2.98e-2 [2.76, 3.23] | 3.21e-2 [2.64, 3.88] | 3.78e-2 [3.17, 4.51] | 2.80e-2 [1.68, 4.64] |
| 5 | 0.01 | 8.34e-2 [7.97, 8.74] | 7.23e-2 [6.88, 7.60] | 6.25e-2 [5.17, 7.55] | 8.94e-2 [7.64, 10.44] | 4.40e-2 [2.92, 6.57] |
| 7 | 0.001 | 1.00e-4 [0.27, 3.65] | 0 [≤ 1.9e-04] | 0 [≤ 3.8e-03] | 0 [≤ 3.8e-03] | – |
| 7 | 0.002 | 4.00e-4 [2.03, 7.89] | 1.50e-4 [0.51, 4.41] | 0 [≤ 3.8e-03] | 0 [≤ 3.8e-03] | – |
| 7 | 0.003 | 1.30e-3 [0.89, 1.90] | 9.50e-4 [6.08, 14.83] | 1.00e-3 [0.18, 5.64] | 4.00e-3 [1.56, 10.24] | – |
| 7 | 0.005 | 1.01e-2 [0.88, 1.16] | 5.45e-3 [4.52, 6.57] | 2.00e-3 [0.55, 7.26] | 5.00e-3 [2.14, 11.65] | – |
| 7 | 0.007 | 3.46e-2 [3.22, 3.73] | 2.31e-2 [2.11, 2.53] | 3.20e-2 [2.28, 4.48] | 4.30e-2 [3.21, 5.74] | – |
| 7 | 0.01 | 0.105 [0.100, 0.109] | 8.30e-2 [7.93, 8.69] | 9.30e-2 [7.65, 11.26] | 0.127 [0.108, 0.149] | – |
Shots per arm: MWPM and correlated MWPM 20 000 everywhere. BP+OSD 20 000 / 5 000 / 1 000 at d = 3 / 5 / 7, fewer where 100 failures came first (7 545, 3 764 and 1 940 at d = 3 for p = 0.005, 0.007, 0.01; 3 120 and 1 599 at d = 5 for p = 0.007, 0.01). ILP 2 000 (d = 3) and 500 (d = 5). Per-seed spread, e.g. d = 5, p = 0.005: correlated MWPM 1.065 / 1.020 / 1.170 ·10⁻² (seed std 7.7·10⁻⁴), BP+OSD-CS 0.72 / 0.60 / 1.32 ·10⁻² (std 3.9·10⁻³). At d = 7, p = 0.005: MWPM 1.02 / 1.08 / 0.93 ·10⁻², correlated 0.51 / 0.645 / 0.48 ·10⁻².
Each cell gives the LER difference [95 % CI] and, in brackets, the number of shots where only the first or only the second decoder failed.
| d | p | shots | BP+OSD-CS − corr. MWPM | McNemar p | corr. MWPM − MWPM (20 000 shots) | McNemar p |
|---|---|---|---|---|---|---|
| 3 | 0.001 | 20000 | +1.0e-03 [+3.9e-04, +1.7e-03] (33/12) | 0.0025 | +3.5e-04 [-5.4e-05, +7.5e-04] (12/5) | 0.14 |
| 3 | 0.002 | 20000 | -7.0e-04 [-1.3e-03, -1.5e-04] (9/23) | 0.02 | -5.0e-05 [-7.1e-04, +6.1e-04] (22/23) | 1 |
| 3 | 0.003 | 20000 | -1.6e-03 [-2.4e-03, -8.7e-04] (15/48) | 3.8e-05 | +7.0e-04 [-8.4e-05, +1.5e-03] (39/25) | 0.1 |
| 3 | 0.005 | 7545 | -1.6e-03 [-3.4e-03, +2.1e-04] (18/30) | 0.11 | -8.5e-04 [-2.0e-03, +2.5e-04] (55/72) | 0.16 |
| 3 | 0.007 | 3764 | -5.8e-03 [-9.0e-03, -2.6e-03] (8/30) | 4.7e-04 | +5.5e-04 [-9.7e-04, +2.1e-03] (125/114) | 0.52 |
| 3 | 0.01 | 1940 | +5.2e-04 [-5.5e-03, +6.5e-03] (18/17) | 1 | -1.1e-03 [-3.0e-03, +7.9e-04] (174/196) | 0.27 |
| 5 | 0.001 | 5000 | 0 (0/0) | 1 | -5.0e-05 [-2.2e-04, +1.2e-04] (1/2) | 1 |
| 5 | 0.002 | 5000 | +4.0e-04 [-3.8e-04, +1.2e-03] (3/1) | 0.62 | -2.0e-04 [-6.2e-04, +2.2e-04] (7/11) | 0.48 |
| 5 | 0.003 | 5000 | -2.0e-04 [-1.1e-03, +6.8e-04] (2/3) | 1 | -1.8e-03 [-2.5e-03, -1.0e-03] (9/44) | 1.2e-06 |
| 5 | 0.005 | 5000 | -1.6e-03 [-3.6e-03, +4.0e-04] (9/17) | 0.17 | -2.4e-03 [-3.7e-03, -1.1e-03] (58/106) | 2.2e-04 |
| 5 | 0.007 | 3120 | +1.3e-03 [-4.0e-03, +6.5e-03] (37/33) | 0.72 | -6.7e-03 [-8.8e-03, -4.6e-03] (162/296) | 3.9e-10 |
| 5 | 0.01 | 1599 | -3.8e-03 [-1.4e-02, +6.8e-03] (34/40) | 0.56 | -1.1e-02 [-1.4e-02, -8.1e-03] (364/586) | 5.9e-13 |
| 7 | 0.001 | 1000 | 0 (0/0) | 1 | -1.0e-04 [-2.4e-04, +3.9e-05] (0/2) | 0.5 |
| 7 | 0.002 | 1000 | 0 (0/0) | 1 | -2.5e-04 [-4.7e-04, -3.1e-05] (0/5) | 0.062 |
| 7 | 0.003 | 1000 | +1.0e-03 [-9.6e-04, +3.0e-03] (1/0) | 1 | -3.5e-04 [-9.0e-04, +2.0e-04] (12/19) | 0.28 |
| 7 | 0.005 | 1000 | -2.0e-03 [-6.8e-03, +2.8e-03] (2/4) | 0.69 | -4.6e-03 [-5.9e-03, -3.4e-03] (33/126) | 5.3e-14 |
| 7 | 0.007 | 1000 | +5.0e-03 [-4.8e-03, +1.5e-02] (15/10) | 0.42 | -1.2e-02 [-1.4e-02, -9.4e-03] (132/363) | 5.8e-26 |
| 7 | 0.01 | 1000 | -1.0e-03 [-1.8e-02, +1.6e-02] (39/40) | 1 | -2.2e-02 [-2.5e-02, -1.8e-02] (549/982) | 1.1e-28 |
| d | p | BP min-sum | BP product-sum | BP-ms converged | no decoder | random corr. | shots MWPM / BP+OSD / BP-ps / ILP |
|---|---|---|---|---|---|---|---|
| 3 | 0.001 | 1.31e-2 [1.16, 1.47] | 1.05e-3 [0.69, 1.60] | 0.965 | 2.17e-2 [1.98, 2.39] | 0.496 | 20 000 / 20 000 / 20 000 / 2 000 |
| 3 | 0.002 | 2.48e-2 [2.28, 2.71] | 4.85e-3 [3.98, 5.91] | 0.927 | 4.47e-2 [4.20, 4.77] | 0.509 | 20 000 / 20 000 / 20 000 / 2 000 |
| 3 | 0.003 | 3.98e-2 [3.71, 4.25] | 8.19e-3 [6.74, 9.95] | 0.877 | 6.69e-2 [6.35, 7.04] | 0.505 | 20 000 / 20 000 / 12 208 / 2 000 |
| 3 | 0.005 | 8.01e-2 [7.41, 8.64] | 2.17e-2 [1.78, 2.63] | 0.778 | 0.105 [0.101, 0.109] | 0.493 | 20 000 / 7 545 / 4 616 / 2 000 |
| 3 | 0.007 | 0.107 [0.097, 0.117] | 4.10e-2 [3.38, 4.96] | 0.698 | 0.136 [0.131, 0.141] | 0.506 | 20 000 / 3 764 / 2 439 / 2 000 |
| 3 | 0.01 | 0.146 [0.131, 0.162] | 7.97e-2 [6.59, 9.60] | 0.578 | 0.185 [0.180, 0.191] | 0.499 | 20 000 / 1 940 / 1 255 / 2 000 |
| 5 | 0.001 | 2.42e-2 [2.03, 2.88] | 1.40e-3 [0.68, 2.89] | 0.881 | 5.73e-2 [5.42, 6.06] | 0.490 | 20 000 / 5 000 / 5 000 / 500 |
| 5 | 0.002 | 4.76e-2 [4.20, 5.39] | 1.20e-2 [0.93, 1.54] | 0.761 | 0.109 [0.105, 0.114] | 0.496 | 20 000 / 5 000 / 5 000 / 500 |
| 5 | 0.003 | 8.52e-2 [7.78, 9.33] | 2.77e-2 [2.28, 3.35] | 0.633 | 0.153 [0.148, 0.158] | 0.487 | 20 000 / 5 000 / 3 614 / 500 |
| 5 | 0.005 | 0.156 [0.146, 0.166] | 7.05e-2 [5.83, 8.50] | 0.370 | 0.230 [0.224, 0.236] | 0.507 | 20 000 / 5 000 / 1 418 / 500 |
| 5 | 0.007 | 0.228 [0.213, 0.243] | 0.139 [0.116, 0.167] | 0.207 | 0.289 [0.283, 0.296] | 0.495 | 20 000 / 3 120 / 718 / 500 |
| 5 | 0.01 | 0.293 [0.272, 0.316] | 0.223 [0.187, 0.264] | 0.095 | 0.351 [0.345, 0.358] | 0.493 | 20 000 / 1 599 / 448 / 500 |
| 7 | 0.001 | 4.50e-2 [3.38, 5.97] | 9.00e-3 [4.74, 17.02] | 0.748 | 0.105 [0.101, 0.109] | 0.492 | 20 000 / 1 000 / 1 000 / – |
| 7 | 0.002 | 8.60e-2 [7.02, 10.50] | 1.90e-2 [1.22, 2.95] | 0.503 | 0.191 [0.186, 0.197] | 0.494 | 20 000 / 1 000 / 1 000 / – |
| 7 | 0.003 | 0.148 [0.127, 0.171] | 5.70e-2 [4.43, 7.31] | 0.329 | 0.254 [0.248, 0.260] | 0.497 | 20 000 / 1 000 / 1 000 / – |
| 7 | 0.005 | 0.235 [0.210, 0.262] | 0.125 [0.104, 0.150] | 0.099 | 0.349 [0.342, 0.356] | 0.512 | 20 000 / 1 000 / 799 / – |
| 7 | 0.007 | 0.316 [0.288, 0.345] | 0.246 [0.206, 0.290] | 0.019 | 0.404 [0.397, 0.411] | 0.497 | 20 000 / 1 000 / 407 / – |
| 7 | 0.01 | 0.413 [0.383, 0.444] | 0.334 [0.283, 0.390] | 0.001 | 0.453 [0.446, 0.460] | 0.497 | 20 000 / 1 000 / 299 / – |
"no decoder" is the raw logical parity of the error. "random corr." is a uniformly random syndrome-consistent correction on the first 5 000 shots. It sits at 0.49–0.51 everywhere: matching the syndrome carries no logical information without a likelihood criterion.
| d | p | MWPM | BP+OSD-CS7 | BP+OSD-0 | BP min-sum | BP product-sum | no decoder |
|---|---|---|---|---|---|---|---|
| 3 | 0.001 | 1.50e-4 [0.51, 4.41] | 1.50e-4 [0.51, 4.41] | 1.50e-4 [0.51, 4.41] | 3.90e-3 [3.13, 4.86] | 1.00e-4 [0.27, 3.65] | 5.50e-3 [4.57, 6.62] |
| 3 | 0.005 | 1.95e-3 [1.43, 2.66] | 1.75e-3 [1.26, 2.43] | 2.20e-3 [1.64, 2.95] | 2.08e-2 [1.89, 2.29] | 2.50e-3 [1.90, 3.29] | 2.88e-2 [2.65, 3.12] |
| 3 | 0.01 | 7.00e-3 [5.94, 8.25] | 6.36e-3 [5.23, 7.73] | 8.21e-3 [6.91, 9.74] | 3.91e-2 [3.61, 4.22] | 8.10e-3 [6.66, 9.84] | 5.55e-2 [5.25, 5.88] |
| 5 | 0.005 | 1.00e-4 [0.27, 3.65] | 5.00e-5 [0.88, 28.32] | 2.00e-4 [0.78, 5.14] | 2.94e-2 [2.72, 3.19] | 1.25e-3 [0.85, 1.84] | 3.72e-2 [3.47, 4.00] |
| 5 | 0.01 | 1.35e-3 [0.93, 1.96] | 1.35e-3 [0.93, 1.96] | 1.55e-3 [1.09, 2.20] | 5.90e-2 [5.58, 6.24] | 9.68e-3 [7.97, 11.76] | 7.31e-2 [6.95, 7.67] |
| 7 | 0.01 | 1.50e-4 [0.51, 4.41] | 1.50e-4 [0.51, 4.41] | 2.50e-4 [1.07, 5.85] | 8.24e-2 [7.87, 8.63] | 1.26e-2 [1.04, 1.53] | 9.55e-2 [9.15, 9.97] |
| 9 | 0.005 | 0 [≤ 1.9e-04] | 0 [≤ 1.9e-04] | 0 [≤ 1.9e-04] | 5.27e-2 [4.96, 5.58] | 3.55e-3 [2.82, 4.48] | 6.07e-2 [5.74, 6.40] |
| 9 | 0.01 | 2.50e-4 [1.07, 5.85] | 2.50e-4 [1.07, 5.85] | 2.00e-4 [0.78, 5.14] | 0.102 [0.098, 0.106] | 1.54e-2 [1.27, 1.87] | 0.114 [0.110, 0.119] |
(Selected rows; the other 16 (d, p) points are in results/ler_table.csv. MWPM and BP+OSD have zero failures in 20 000 shots at d ≥ 5 for most p ≤ 0.003.) The repetition DEM is a graph, so correlated MWPM equals MWPM at all 24 points. MWPM, BP+OSD-CS and BP+OSD-0 agree within CIs everywhere. The LER falls with d (within CIs) for every decoder except BP alone, and no crossing appears below p = 0.01 (threshold above the grid). BP min-sum is 6–400× worse than MWPM even on this graph-like DEM, and it also gets worse with d.
| code | p | BP+OSD-CS7 | BP+OSD-0 | BP min-sum | BP product-sum | exact MW (ILP) | BP-ms conv. | shots BP+OSD / BP-ps / ILP |
|---|---|---|---|---|---|---|---|---|
| [[72,12,6]] | 0.01 | 2.30e-3 [1.72, 3.07] | 2.40e-3 [1.81, 3.18] | 2.80e-3 [2.16, 3.63] | 3.00e-3 [2.33, 3.86] | 1.50e-3 [0.51, 4.40] | 0.999 | 20 000 / 20 000 / 2 000 |
| [[72,12,6]] | 0.02 | 2.42e-2 [1.99, 2.93] | 2.47e-2 [2.04, 2.99] | 2.86e-2 [2.39, 3.41] | 2.74e-2 [2.26, 3.32] | 1.50e-2 [1.05, 2.13] | 0.988 | 4 133 / 3 651 / 2 000 |
| [[72,12,6]] | 0.03 | 7.25e-2 [5.99, 8.74] | 7.97e-2 [6.66, 9.52] | 9.13e-2 [7.72, 10.77] | 8.90e-2 [7.37, 10.70] | 5.89e-2 [4.86, 7.11] | 0.961 | 1 380 / 1 124 / 1 699 |
| [[72,12,6]] | 0.04 | 0.202 [0.169, 0.240] | 0.218 [0.184, 0.257] | 0.255 [0.218, 0.295] | 0.217 [0.182, 0.257] | 0.188 [0.157, 0.223] | 0.887 | 495 / 460 / 532 |
| [[72,12,6]] | 0.05 | 0.303 [0.256, 0.355] | 0.306 [0.259, 0.358] | 0.342 [0.293, 0.395] | 0.319 [0.270, 0.373] | 0.303 [0.256, 0.355] | 0.865 | 330 / 313 / 330 |
| [[72,12,6]] | 0.06 | 0.463 [0.398, 0.530] | 0.481 [0.416, 0.548] | 0.509 [0.443, 0.575] | 0.483 [0.416, 0.551] | 0.441 [0.377, 0.506] | 0.782 | 216 / 207 / 227 |
| [[72,12,6]] | 0.08 | 0.735 [0.655, 0.802] | 0.765 [0.687, 0.828] | 0.824 [0.751, 0.878] | 0.775 [0.696, 0.839] | 0.752 [0.672, 0.818] | 0.592 | 136 / 129 / 133 |
| [[72,12,6]] | 0.10 | 0.935 [0.871, 0.968] | 0.935 [0.871, 0.968] | 0.953 [0.895, 0.980] | 0.943 [0.882, 0.974] | 0.943 [0.882, 0.974] | 0.416 | 107 / 106 / 106 |
| [[72,12,6]] | 0.12 | 0.943 [0.882, 0.974] | 0.943 [0.882, 0.974] | 0.953 [0.894, 0.980] | 0.952 [0.893, 0.979] | 0.943 [0.882, 0.974] | 0.401 | 106 / 105 / 106 |
| [[108,8,10]] | 0.01 | 3.50e-4 [1.70, 7.22] | 1.80e-3 [1.30, 2.49] | 7.50e-4 [4.55, 12.37] | 8.50e-4 [5.31, 13.61] | – | 0.999 | 20 000 / 20 000 / – |
| [[108,8,10]] | 0.02 | 2.65e-3 [2.03, 3.46] | 7.80e-3 [6.67, 9.12] | 7.15e-3 [6.07, 8.42] | 5.60e-3 [4.61, 6.80] | – | 0.993 | 20 000 / 17 864 / – |
| [[108,8,10]] | 0.03 | 8.39e-3 [6.90, 10.19] | 2.31e-2 [2.05, 2.59] | 3.45e-2 [3.14, 3.80] | 2.21e-2 [1.82, 2.68] | – | 0.973 | 11 925 / 4 530 / – |
| [[108,8,10]] | 0.04 | 2.43e-2 [2.00, 2.95] | 5.35e-2 [4.71, 6.08] | 0.109 [0.100, 0.119] | 7.14e-2 [5.90, 8.61] | – | 0.931 | 4 110 / 1 401 / – |
| [[108,8,10]] | 0.05 | 5.29e-2 [4.37, 6.40] | 0.112 [0.099, 0.127] | 0.230 [0.211, 0.249] | 0.153 [0.127, 0.183] | – | 0.863 | 1 889 / 654 / – |
| [[108,8,10]] | 0.06 | 0.151 [0.125, 0.180] | 0.244 [0.213, 0.278] | 0.413 [0.376, 0.450] | 0.309 [0.261, 0.361] | – | 0.753 | 664 / 324 / – |
| [[108,8,10]] | 0.08 | 0.380 [0.324, 0.440] | 0.551 [0.491, 0.610] | 0.749 [0.693, 0.798] | 0.671 [0.592, 0.741] | – | 0.466 | 263 / 149 / – |
| [[108,8,10]] | 0.10 | 0.769 [0.690, 0.833] | 0.854 [0.783, 0.904] | 0.938 [0.883, 0.968] | 0.926 [0.861, 0.962] | – | 0.231 | 130 / 108 / – |
| [[108,8,10]] | 0.12 | 0.926 [0.861, 0.962] | 0.981 [0.935, 0.995] | 0.981 [0.935, 0.995] | 0.980 [0.931, 0.995] | – | 0.148 | 108 / 102 / – |
| [[144,12,12]] | 0.01 | 2.00e-4 [0.78, 5.14] | 1.25e-3 [0.85, 1.84] | 1.05e-3 [0.69, 1.60] | 1.30e-3 [0.89, 1.90] | – | 0.999 | 20 000 / 20 000 / – |
| [[144,12,12]] | 0.02 | 1.85e-3 [1.34, 2.55] | 8.60e-3 [7.41, 9.98] | 7.55e-3 [6.44, 8.85] | 7.18e-3 [5.91, 8.72] | – | 0.992 | 20 000 / 13 928 / – |
| [[144,12,12]] | 0.03 | 6.58e-3 [5.41, 7.99] | 2.18e-2 [1.96, 2.43] | 3.23e-2 [2.96, 3.52] | 1.82e-2 [1.50, 2.21] | – | 0.975 | 15 201 / 5 481 / – |
| [[144,12,12]] | 0.04 | 1.93e-2 [1.59, 2.34] | 5.36e-2 [4.78, 6.01] | 9.92e-2 [9.13, 10.76] | 6.70e-2 [5.54, 8.08] | – | 0.934 | 5 184 / 1 493 / – |
| [[144,12,12]] | 0.05 | 5.76e-2 [4.76, 6.96] | 0.116 [0.102, 0.132] | 0.225 [0.206, 0.245] | 0.139 [0.115, 0.166] | – | 0.866 | 1 735 / 722 / – |
| [[144,12,12]] | 0.06 | 0.147 [0.122, 0.175] | 0.224 [0.195, 0.257] | 0.362 [0.327, 0.399] | 0.254 [0.214, 0.300] | – | 0.772 | 682 / 393 / – |
| [[144,12,12]] | 0.08 | 0.552 [0.480, 0.623] | 0.657 [0.586, 0.723] | 0.785 [0.719, 0.838] | 0.746 [0.666, 0.812] | – | 0.481 | 181 / 134 / – |
| [[144,12,12]] | 0.10 | 0.826 [0.749, 0.884] | 0.909 [0.845, 0.948] | 0.959 [0.907, 0.982] | 0.935 [0.871, 0.968] | – | 0.207 | 121 / 107 / – |
| [[144,12,12]] | 0.12 | 0.980 [0.931, 0.995] | 0.980 [0.931, 0.995] | 1.000 [0.964, 1.000] | 1.000 [0.963, 1.000] | – | 0.078 | 102 / 100 / – |
LER is the block error rate: a shot fails if any of the k logical qubits flips, in either the X or the Z sector. "No decoder" (raw logical parity) is 0.568 / 0.633 / 0.754 already at p = 0.01, and the random consistent correction is 1.000 everywhere: a random coset flips one of 12 logicals with probability 1 − 2⁻¹². MWPM is not applicable. PyMatching raises ValueError: check_matrix must contain at most two ones per column, but column 0 has 3 ones for every BB code, which is recorded in results.json.
Paired, on identical shots: BP+OSD-CS beats BP+OSD-0 on [[144,12,12]] at every p from 0.01 to 0.10 (e.g. p = 0.02: −6.75·10⁻³, McNemar p = 2.8·10⁻³⁸; p = 0.05: −0.058, p = 2.1·10⁻²⁹), and likewise on [[108,8,10]] (p ≤ 0.031 at all nine points). On [[72,12,6]] OSD-CS vs OSD-0 differs significantly only at p = 0.03 and 0.04 (−0.0072, p = 0.002; −0.016, p = 0.008). The OSD order matters more on the larger codes.
| family | decoder | pair | crossing p | grid bracket | bootstrap 95 % | bootstrap reps with a crossing |
|---|---|---|---|---|---|---|
| surface | MWPM | d = 3 → 5 | 0.0063 | 0.005–0.007 | [0.0058, 0.0068] | 1.00 |
| surface | MWPM | d = 5 → 7 | 0.0075 | 0.007–0.01 | [0.0066, 0.0081] | 1.00 |
| surface | correlated MWPM | d = 3 → 5 | 0.0077 | 0.007–0.01 | [0.0069, 0.0083] | 1.00 |
| surface | correlated MWPM | d = 5 → 7 | 0.0088 | 0.007–0.01 | [0.0082, 0.0093] | 1.00 |
| surface | BP+OSD-CS7 | d = 3 → 5 | 0.0063 | 0.005–0.007 | [0.0055, 0.0078] | 0.99 |
| surface | BP+OSD-CS7 | d = 5 → 7 | 0.0070 | 0.007–0.01 | [0.0062, 0.0087] | 0.97 |
| surface | BP+OSD-0 | d = 3 → 5 | 0.0048 | 0.003–0.005 | [0.0033, 0.0067] | 1.00 |
| surface | BP+OSD-0 | d = 5 → 7 | 0.0068 | 0.005–0.007 | [0.0062, 0.0082] | 0.99 |
| surface | BP min-sum / product-sum | all pairs | none: larger d worse on the whole grid | – | – | 0.00 / ≤ 0.28 |
| repetition | MWPM, corr. MWPM, BP+OSD-CS | all pairs | none: larger d better on the whole grid (threshold > 0.01) | – | – | 0.00 |
| BB | BP+OSD-CS7 | [[72,12,6]] → [[144,12,12]] | 0.115 | 0.10–0.12 | [0.107, 0.119] | 0.91 |
| BB | BP+OSD-CS7 | [[108,8,10]] → [[144,12,12]] | 0.047 | 0.04–0.05 | [0.020, 0.067] | 1.00 |
| BB | BP+OSD-CS7 | [[72,12,6]] → [[108,8,10]] | none on grid | – | – | 0.34 |
| BB | BP min-sum | [[72,12,6]] → [[144,12,12]] | 0.098 | 0.08–0.10 | [0.076, 0.111] | 1.00 |
The grid has 6 (circuit) or 9 (capacity) points, so every crossing is an interpolation between two grid points. The bootstrap interval covers binomial noise only, not the interpolation error. The two surface-code crossings drift upward with d for every decoder, the usual finite-size effect. The BB "crossings" sit where both codes already fail on 90 %+ of shots (72/144) or compare codes with different k (108/144), so they are not thresholds. Below them, [[144,12,12]] is better than [[72,12,6]] at every p ≤ 0.10.
| instance | p | MWPM | corr. MWPM | BP min-sum | BP product-sum | BP+OSD-0 | BP+OSD-CS7 | ILP |
|---|---|---|---|---|---|---|---|---|
| surface d = 3 | 0.001 | 0.054 | 0.137 | 8.9 | 8.0 | 10.1 | 13.3 | 612 |
| surface d = 3 | 0.005 | 0.211 | 0.635 | 40.5 | 36.7 | 44.7 | 73.7 | 2 910 |
| surface d = 3 | 0.01 | 0.461 | 1.24 | 58 | 104 | 65 | 114 | 3 870 |
| surface d = 5 | 0.001 | 0.34 | 0.89 | 317 | 430 | 345 | 1 030 | 16 600 |
| surface d = 5 | 0.005 | 2.57 | 5.71 | 1 190 | 2 330 | 1 190 | 3 930 | 33 600 |
| surface d = 5 | 0.01 | 4.76 | 11.5 | 1 560 | 4 270 | 1 750 | 6 450 | 109 000 |
| surface d = 7 | 0.001 | 1.02 | 3.04 | 1 800 | 2 550 | 1 930 | 18 100 | n/a |
| surface d = 7 | 0.005 | 6.39 | 17.0 | 5 150 | 11 300 | 5 840 | 50 000 | n/a |
| surface d = 7 | 0.01 | 22.1 | 63.8 | 8 710 | 24 600 | 7 450 | 64 800 | n/a |
| repetition d = 9 | 0.005 | 0.42 | 1.04 | 25 | 23 | 28 | 43 | n/a |
| BB [[72,12,6]] | 0.05 | n/a | n/a | 31 | 74 | 37 | 49 | 13 000 |
| BB [[108,8,10]] | 0.05 | n/a | n/a | 47 | 112 | 56 | 76 | n/a |
| BB [[144,12,12]] | 0.05 | n/a | n/a | 73 | 163 | 91 | 127 | n/a |
MWPM is timed through decode_batch over all 20 000 shots. Every other decoder is timed through per-shot Python calls on the first ≤ 300 shots after a 20-shot warm-up. The measured ldpc call overhead on an all-zero syndrome is 1.3 µs (d = 3), 5.4 µs (d = 5) and 15–16 µs (d = 7), mostly copying the n-long output vector, so it is irrelevant beyond d = 3. ILP times include trivial shots. The ILP was not run on the d = 7 grid; §5.9 gives its time per non-trivial syndrome there. BP+OSD-CS runs slower than OSD-0 because ldpc's OSD-CS does a weight-1 sweep over all n − rank non-pivot columns (5 135 at d = 7) plus a weight-2 sweep over the first 7. Ratios at d = 7: BP+OSD-CS / correlated MWPM ≈ 6 000× (p = 0.001), 2 900× (p = 0.005), 1 000× (p = 0.01).
Distance to the ILP optimum on identical shots. "Heavier" is the fraction of shots whose (always syndrome-valid) correction has a larger Σ w_j e_j than the ILP optimum. No decoder was ever lighter than the ILP (frac_weight_below_optimum = 0 everywhere), which checks the ILP. The ILP − X columns are paired LER differences, with the McNemar p in brackets.
| surface d = 3, p | ILP LER (2 000 shots) | BP+OSD-CS heavier | BP+OSD-0 heavier | ILP − BP+OSD-CS | ILP − MWPM | ILP − corr. MWPM |
|---|---|---|---|---|---|---|
| 0.001 | 0.0005 | 0.0035 | 0.0045 | −0.0035 (0.016) | +0.0005 (1) | −0.0010 (0.62) |
| 0.002 | 0.0035 | 0.0005 | 0.0065 | −0.0005 (1) | −0.0015 (0.25) | −0.0020 (0.12) |
| 0.003 | 0.0065 | 0.0000 | 0.0115 | 0.0000 (1) | +0.0015 (0.38) | −0.0010 (0.69) |
| 0.005 | 0.0155 | 0.0060 | 0.0290 | +0.0005 (1) | −0.0020 (0.45) | +0.0005 (1) |
| 0.007 | 0.0260 | 0.0120 | 0.0665 | −0.0005 (1) | −0.0065 (0.015) | −0.0080 (0.0015) |
| 0.01 | 0.0495 | 0.0072 | 0.1387 | −0.0005 (1) | −0.0015 (0.76) | −0.0010 (0.87) |
| surface d = 5, p | ILP LER (500 shots) | BP+OSD-CS heavier | BP+OSD-0 heavier | ILP − BP+OSD-CS | ILP − MWPM | ILP − corr. MWPM |
|---|---|---|---|---|---|---|
| 0.001 | 0.0000 | 0.0020 | 0.0180 | 0.0000 (1) | 0.0000 (1) | 0.0000 (1) |
| 0.003 | 0.0020 | 0.0220 | 0.0980 | 0.0000 (1) | 0.0000 (1) | 0.0000 (1) |
| 0.005 | 0.0040 | 0.0400 | 0.2120 | −0.0020 (1) | −0.0040 (0.62) | −0.0040 (0.5) |
| 0.007 | 0.0280 | 0.0800 | 0.3700 | 0.0000 (1) | −0.0140 (0.14) | −0.0020 (1) |
| 0.01 | 0.0440 | 0.1740 | 0.5600 | −0.0100 (0.23) | −0.0300 (0.0059) | −0.0180 (0.064) |
| [[72,12,6]], p | ILP LER | ILP shots | BP+OSD-CS heavier | BP+OSD-0 heavier | BP-ms invalid | ILP − BP+OSD-CS |
|---|---|---|---|---|---|---|
| 0.01 | 0.0015 | 2 000 | 0.0010 | 0.0015 | 0.004 | −0.0020 (0.29) |
| 0.02 | 0.0150 | 2 000 | 0.0100 | 0.0125 | 0.024 | −0.0090 (0.0051) |
| 0.03 | 0.0589 | 1 699 | 0.0130 | 0.0239 | 0.076 | −0.0138 (0.034) |
| 0.04 | 0.1880 | 532 | 0.0202 | 0.0525 | 0.212 | −0.0121 (0.5) |
| 0.05 | 0.3030 | 330 | 0.0182 | 0.0545 | 0.255 | 0.0000 (1) |
| 0.08 | 0.7519 | 133 | 0.0376 | 0.1203 | 0.684 | +0.0150 (0.83) |
At d = 3 the heavier fraction of BP min-sum's valid outputs is small, but 3.5–42 % of its outputs do not reproduce the syndrome at all (frac_invalid_correction 0.035 at p = 0.001 up to 0.422 at p = 0.01). The mean excess weight of BP+OSD-CS's heavier corrections at d = 3, p = 0.001 is 26.65 in units of ln((1−p)/p). This is the failure mode below.
BP flavour inside BP+OSD-CS7 (same shots per row group; heavy = fraction of shots where BP converged to a syndrome-valid correction heavier than the ILP optimum, so OSD never ran):
| instance (shots) | decoder | failures | LER [95 % CI] | heavy (conv.) | failures from heavy |
|---|---|---|---|---|---|
| surface d = 3, p = 0.001 (20 000) | MWPM | 20 | 1.00e-3 [6.5e-4, 1.5e-3] | – | – |
| correlated MWPM | 23 | 1.15e-3 [7.7e-4, 1.7e-3] | – | – | |
| min-sum 0.625, parallel (main arm) | 31 | 1.55e-3 [1.1e-3, 2.2e-3] | 0.0012 | 21 | |
| min-sum 1.0, parallel | 12 | 6.0e-4 [3.4e-4, 1.0e-3] | 0.0026 | 2 | |
| product-sum, parallel | 18 | 9.0e-4 [5.7e-4, 1.4e-3] | 0.0042 | 7 | |
| min-sum 0.625, serial | 10 | 5.0e-4 [2.7e-4, 9.2e-4] | 0.00005 | 0 | |
| surface d = 3, p = 0.005 (20 000) | MWPM / corr. MWPM | 340 / 325 | 1.70e-2 / 1.63e-2 | – | – |
| ms 0.625 par. / ms 1.0 par. / product-sum / ms 0.625 serial | 299 / 387 / 300 / 296 | 1.49e-2 / 1.93e-2 / 1.50e-2 / 1.48e-2 | – | – | |
| surface d = 5, p = 0.003 (3 000) | MWPM / corr. MWPM | 14 / 9 | 4.67e-3 / 3.00e-3 | – | – |
| ms 0.625 par. / ms 1.0 par. / product-sum / ms 0.625 serial | 8 / 9 / 8 / 6 | 2.67e-3 / 3.00e-3 / 2.67e-3 / 2.00e-3 | – | – | |
| [[144,12,12]], p = 0.05 (5 000) | ms 0.625 par. / ms 1.0 par. / product-sum / ms 0.625 serial | 333 / 4 162 / 367 / 304 | 6.66e-2 / 0.832 / 7.34e-2 / 6.08e-2 | – | – |
With the cache, the serial schedule took 2.43 s vs 0.58 s at d = 3, p = 0.005 and 26.3 s vs 7.25 s at d = 5 (about 4× slower).
BP iteration budget (same shots for all budgets; BP+OSD group, µs per shot for the whole group):
| instance | iterations | BP min-sum | BP+OSD-0 | BP+OSD-CS7 | µs/shot |
|---|---|---|---|---|---|
| surface d = 5, p = 0.005 (1 000 shots) | 10 | 0.1650 | 0.0120 | 0.0090 | 3 450 |
| 30 | 0.1640 | 0.0120 | 0.0070 | 3 736 | |
| 50 (main) | 0.1640 | 0.0120 | 0.0070 | 5 083 | |
| 100 | 0.1640 | 0.0120 | 0.0070 | 7 661 | |
| [[144,12,12]], p = 0.05 (2 000 shots) | 10 | 0.3050 | 0.0975 | 0.0570 | 221 |
| 30 | 0.2430 | 0.1190 | 0.0640 | 249 | |
| 50 (main) | 0.2385 | 0.1190 | 0.0655 | 340 | |
| 100 | 0.2340 | 0.1235 | 0.0635 | 272 |
| instance | ILP variables / constraints | solves | mean / median / max per non-trivial syndrome | time-limit hits (10 s) |
|---|---|---|---|---|
| surface d = 3, p = 0.005 | 243 / 24 | 20 | 5.6 / 5.1 / 9.8 ms | 0 |
| surface d = 5, p = 0.005 | 1 797 / 120 | 20 | 29.7 / 26.4 / 49.8 ms | 0 |
| surface d = 7, p = 0.005 | 5 807 / 336 | 10 | 405 / 236 / 1 310 ms | 0 |
| [[72,12,6]], p = 0.05 (one sector) | 108 / 36 | 20 | 11.1 / 6.0 / 58.3 ms | 0 |
| [[108,8,10]], p = 0.05 | 162 / 54 | 20 | 10.6 / 6.6 / 54.6 ms | 0 |
| [[144,12,12]], p = 0.05 | 216 / 72 | 20 | 7.2 / 7.0 / 11.4 ms | 0 |
Distances by ILP (min |x| s.t. H_Z x = 0, L_Z[j]·x = 1): [[72,12,6]] gives weight 6 for all 12 logicals, all proven optimal, in 5.1 s total. [[108,8,10]], logical 0: weight 10, proven, 6.7 s. [[144,12,12]], logical 0: incumbent 12, not proven within the 20 s limit. So d = 12 is only confirmed as an upper bound here; the cited value is from Bravyi et al.
- Surface code, d ≥ 5: correlated matching and BP+OSD-CS are tied, both beat plain MWPM. Correlated MWPM beats plain MWPM at d = 5 for p ≥ 0.003 and at d = 7 for p ≥ 0.005 (McNemar p from 2.2·10⁻⁴ down to 10⁻²⁸), by up to 1.85× at d = 7, p = 0.005. BP+OSD-CS against correlated MWPM is never significant at d = 5 or 7 (p = 0.17–1). BP+OSD-CS's point estimates (e.g. 2.0·10⁻³ vs 5.45·10⁻³ at d = 7, p = 0.005) rest on 1 000–5 000 shots and 2–100 failures.
- At d = 3 BP+OSD-CS is best at mid p, worst at low p. It beats correlated MWPM at p = 0.002, 0.003, 0.007 (McNemar p = 0.02, 4·10⁻⁵, 5·10⁻⁴) but loses at p = 0.001 (1.95·10⁻³ vs MWPM 5.5·10⁻⁴; vs correlated MWPM +1.0·10⁻³, p = 0.0025). The cause is identified in §5.8. With min-sum scaling 0.625, BP converges on 0.12 % of shots to a syndrome-valid correction heavier than the optimum (mean excess weight 26.65, i.e. about e²⁷ times less likely). OSD is skipped on those shots, and 21 of the 31 failures come from them. A serial schedule removes them (10 failures vs MWPM's 20 on the same 20 000 shots).
- No single BP flavour is safe. Unscaled min-sum (scaling 1.0) is best at d = 3, p = 0.001 but worst at d = 3, p = 0.005 (387 vs 299 failures). On [[144,12,12]] it collapses to LER 0.832 against 0.067 for scaling 0.625. Serial min-sum 0.625 was never worse than the main arm, at about 4× the time on the surface code (the same time on [[144,12,12]]).
- BP alone fails on the surface code and has no threshold. Its LER rises with d at every p, for both min-sum and product-sum. Convergence falls from 0.965 (d = 3, p = 0.001) to 0.001 (d = 7, p = 0.01). At p = 0.001 product-sum is 5–17× better than min-sum, but still 90× worse than MWPM at d = 7.
- On BB codes BP+OSD-CS is the decoder, and OSD-CS earns its cost on the larger codes. On [[144,12,12]] it is 4.6× better than OSD-0 at p = 0.02 (1.85·10⁻³ vs 8.6·10⁻³) and 2.0× at p = 0.05, for 1.4× the time (127 vs 91 µs). BP alone converges on 87–99.9 % of shots at p ≤ 0.05 there, yet at p ≤ 0.05 BP min-sum stays 4–5× and product-sum 2.4–6.5× worse than BP+OSD-CS.
- The exact minimum-weight decoder is not always the ceiling, and BP+OSD is not always near it. On [[72,12,6]] the ILP beats BP+OSD-CS at p = 0.02 and 0.03 (paired −0.009 and −0.014). At p ≥ 0.05, where degeneracy dominates, it no longer does. On the surface code at d = 3 the ILP ties BP+OSD-CS at every p except 0.001. At d = 5, p = 0.01 it is better than plain MWPM by 0.030 (p = 0.006) on 500 shots, while BP+OSD-CS returns a heavier-than-optimal correction on 17 % of those shots and loses only 0.010 (p = 0.23).
- Cost. On the surface code the decoders span 5–6 orders of magnitude per shot: MWPM 0.05–22 µs, correlated MWPM 0.14–64 µs, BP 9 µs–25 ms, BP+OSD-CS 13 µs–65 ms, ILP 0.6–109 ms (d ≤ 5). Only matching comes close to the ~1 µs cycle time of superconducting hardware: MWPM takes 6.4 µs per 7-round d = 7 shot at p = 0.005 on one loaded core.
A memory experiment the Open Plan Sampler can run (final measurements only): d data qubits interleaved with d − 1 ancillas on a
25-qubit line (codes nested on the same physical path, data on even positions), data prepared in |0…0⟩ or |1…1⟩, an optional
idle delay τ on the data, one round of ZZ-parity extraction (two CX layers), then everything measured. 24 circuits × 4 000
shots in one job (27 QPU seconds), raw counts (scripts/hardware_run_ibm.py; record
results/hardware/exp37-repetition-memory_ibm_fez_db1afrqvog1s73fhskag.json). Decoding uses this experiment's own machinery: Stim's
repetition_code:memory model with rounds = 1 and PyMatching MWPM at prior p = 0.01 (detectors = ancilla bits and
ancilla ⊕ data_i ⊕ data_{i+1}; observable = the last data bit), cross-checked against explicit formulas and against majority
vote on the data bits (they agree on every trivial-syndrome shot). Calibration on the 25 qubits: median CZ error
2.3e-03, median readout error 0.7 %. Λ = LER(d) / LER(d + 2) from a binomial maximum-likelihood fit of log LER vs d
(profile-likelihood 95 % CI); p = the uniform physical error at which the rounds = 1 model decoded by the same decoder reproduces
the measured LERs.
| series | d = 3 | 5 | 7 | 9 | 11 | 13 | Λ per d → d + 2 | fitted p (95 % CI) | raw flip rates data / ancilla |
|---|---|---|---|---|---|---|---|---|---|
| |0…0⟩, τ = 0 | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | – | 0.0005 [0.0005, 0.0038] | 0.003–0.004 / 0.023–0.036 |
| |1…1⟩, τ = 0 | 1.0e-03 (4/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | > 2.6 (one failure at d = 3) | 0.0050 [0.0030, 0.0083] | 0.013–0.013 / 0.024–0.037 |
| |1…1⟩, τ = 2 µs | 2.7e-03 (11/4000) | 2.5e-04 (1/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | < 7.5e-04 (0/4000) | 12.9 [3.4, 219] | 0.0093 [0.0071, 0.0116] | 0.031–0.035 / 0.062–0.072 |
| |1…1⟩, τ = 10 µs | 2.5e-02 (98/4000) | 4.0e-03 (16/4000) | 1.3e-03 (5/4000) | 5.0e-04 (2/4000) | 2.5e-04 (1/4000) | 2.5e-04 (1/4000) | 4.0 [3.1, 5] | 0.0278 [0.0257, 0.0305] | 0.088–0.106 / 0.159–0.191 |
- Below threshold on the real device. With 10 µs of idling the logical error falls 2.5e-02 → 2.5e-04 from d = 3 to 13, Λ = 4.0 [3.1, 5.3] per two units of distance at p = 0.028; with 2 µs, 2.7e-03 → < 7.5 × 10⁻⁴ (no failure from d = 7) at p ≈ 0.009. Without idling |1…1⟩ fails 4 times in 4 000 shots at d = 3 and never above, and |0…0⟩ never fails at any d: the |0⟩ family is readout-limited (data flip 0.3–0.6 %) and is a null control, since the ground state cannot decay.
- What the physical error is made of. The data-qubit flip rate grows 0.4 % (|0⟩) → 1.3 % (|1⟩, τ = 0) → 3.3 % (2 µs) → 9–11 % (10 µs): a T1 effect (readout asymmetry 1.4 % vs 0.4 % for prepared 1 vs 0 on the data qubits). Ancilla flips are 2–4 % without idling (two CX plus readout) and 16–19 % with 10 µs idling, because the ancilla sees the data's decay through the parity. The fitted uniform p matches the data-flip-implied p within 10 % in every series, so the rounds = 1 model is adequate.
- One bad qubit. Physical qubit 69 (an ancilla) flips 10 % of the time even with |0…0⟩ and no idling (median ancilla 2.8 %);
the decoder absorbs it at d ≥ 5 but it is the dominant syndrome-weight error at d = 3 (
metrics.flip_maphas every qubit). - Against §5.4. Experiment 37's rounds = d repetition code at the nearest grid p reproduces the shape: at p = 0.005 the simulated MWPM LER is 1.9e-03 at d = 3 and 0 from d = 7; the device's τ = 0 series (fitted p = 0.005) gives 1.0e-03 and 0. The 10 µs series (p ≈ 0.028) is outside the simulated grid (p ≤ 0.01) and is the one that resolves Λ; a rounds = d experiment at that p would be far above the circuit-level threshold region of §5.6, so the comparison is on the code-capacity-like regime only.
- Majority vote = MWPM here. With a single round and the final data readout, matching only beats majority vote when an error straddles the round; the two decoders differ on one circuit (d = 5, 10 µs: 4.75e-03 vs 4.00e-03). The decoder comparison of §5.1–5.3 needs mid-circuit measurement, which this job type does not have.
Which decoder wins where, and at what cost. On the surface code, correlated MWPM is the Pareto choice. At d = 5 and 7 it cannot be told apart from BP+OSD-CS on identical shots, and it is 560–6 000× cheaper. Plain MWPM loses up to 1.85× to both at d = 7 because decomposition throws away the correlations of the 3 793 hyperedge mechanisms (of 5 471); BP+OSD and the ILP see the undecomposed DEM. PyMatching's two-pass correlation recovers most of that loss at 2–3× the cost of plain matching. At d = 3 the DEM is small enough that OSD-CS costs ≤ 114 µs per shot, and there BP+OSD-CS has a real edge at mid p (−5.8·10⁻³ against correlated MWPM at p = 0.007). On the BB codes MWPM does not apply and BP+OSD-CS is the best practical decoder we ran. The OSD-CS sweep matters more as the code grows (4.6× over OSD-0 on [[144,12,12]] at p = 0.02, no significant gain on [[72,12,6]] at p ≤ 0.02). BP+OSD-CS is still measurably sub-optimal on the smallest code at low p, where exact minimum-weight decoding beats it.
BP alone and the degeneracy problem. Surface codes are highly degenerate: many corrections of equal weight differ by a stabilizer. Their DEM Tanner graph is full of short cycles. BP's marginals cannot break the symmetry between equally good corrections, so it oscillates. Its hard decision then violates the syndrome on up to 42 % of shots at d = 3 (p = 0.01), and it converges on only 0.1 % of shots at d = 7, p = 0.01. The result is an LER that increases with distance, i.e. no threshold for either min-sum or product-sum. This is the classic failure analysed by Poulin & Chung (arXiv:0801.1241) and the motivation for OSD post-processing (Panteleev & Kalachev). On the BB codes under code capacity BP converges far more often (87–99.9 % at p ≤ 0.05) but is still 2.4–6.5× worse than BP+OSD-CS.
The flip side is the low-p failure of BP+OSD itself (§5.8 and §5.10, observation 2): if BP converges to a wrong but valid correction, OSD never runs. We diagnosed the d = 3, p = 0.001 case offline, outside run.py, so the following is not a results.json quantity. The dominant case was one recurring syndrome with four detection events. Its optimum is a single hyperedge mechanism of weight 7.42, and min-sum BP with scaling 0.625 settled on four separate edge mechanisms of total weight 34.07. The difference, 26.65, is exactly the mean excess weight recorded in results.json. The BP-flavour study shows no universal fix: scaling 1.0 repairs this case and wrecks [[144,12,12]], and the serial schedule is robust here but about 4× slower. The number published for "BP+OSD" therefore depends on BP settings that are rarely reported.
The exact reference and its size limit. The ILP returns the most likely error, not the most likely logical class, which would be the optimal (degenerate maximum-likelihood) decoder and is #P-hard in general. It is therefore a reference, not a ceiling: at p ≥ 0.05 on [[72,12,6]] BP+OSD-CS ties or beats it, and at d = 3 on the surface code it is statistically tied with BP+OSD-CS at five of six points. Its time per non-trivial syndrome is 5.6 ms (d = 3), 30 ms (d = 5) and 0.41 s mean / 1.31 s max (d = 7, 5 807 variables), with no hit of the 10 s limit. So exact minimum-weight decoding of a 7-round d = 7 circuit-level DEM is feasible offline. We did not run it on the d = 7 grid because 20 000 shots would cost about 2 h per grid point, not because it failed. The honest statement is: up to d = 7 the exact minimum-weight correction costs a median 0.24 s (max 1.3 s) per non-trivial syndrome on this laptop, 10⁴–10⁵× the cost of matching. The d = 5 ILP arm used only 500 shots, which is enough for the weight statistics (e.g. BP+OSD-CS heavier than optimal on 17 % of shots at p = 0.01) but not for LER differences below ~10⁻². For the distance proofs the limit is reached earlier. [[72,12,6]] is proven in 5 s, but a single logical of [[144,12,12]] is not proven within 20 s.
Thresholds. The crossings (MWPM 0.63 % / 0.75 %, correlated 0.77 % / 0.88 %, BP+OSD-CS 0.63 % / 0.70 %) come from a 6-point grid and drift upward with d. They are finite-size estimates of the pseudo-threshold of this particular uniform noise model, not asymptotic thresholds. They are of the same order as the ≈ 0.57 % reported by Fowler et al. (2012) for MWPM under a similar uniform model, and the exact value depends on the noise details. BP+OSD-CS's d = 5/7 bootstrap interval is wide ([0.62 %, 0.87 %]) because its d = 7 points rest on 1 000 shots.
Equal budgets. Every BP-based arm has the same 50-iteration budget. BP+OSD-CS is flat from 30 to 100 iterations on the surface code (7 failures in 1 000 shots at each) and within noise on [[144,12,12]] (0.057–0.066). BP alone on [[144,12,12]] still gains from 10 to 30 iterations (0.305 → 0.243), so its row is not iteration-starved at 50. The OSD order was fixed at 7, a common choice, and not swept.
Statistics. Every point has ≥ 100 failures or the stated shot cap. Where BP+OSD ran on 1 000 shots (d = 7) with 0–93 failures, "tied with correlated MWPM" means "not distinguishable at this budget". The paired McNemar tests are the basis for every comparative claim above, rather than overlapping marginal CIs. The 100-failure stopping rule is inverse sampling (slight upward bias in LER, negligible at 100 failures). In the examples of §5.1 the per-seed LERs agree within binomial noise; all per-seed values are in results.json (ler_per_seed, ler_seed_std).
Timing. The machine ran three sibling experiments during the full run (load average 17–56 on 10 cores), so absolute times may be up to ~2× pessimistic. ldpc has no batch API in 2.4.1 and is called per shot from Python (1.3–16 µs overhead measured), while PyMatching decodes in batch. Neither affects the 10³× ratios that carry the conclusions.
What is not here. No hardware data: all noise is Stim's uniform circuit-level model, with no leakage, crosstalk or drift (see experiment 11 for why that matters to learned decoders). The BB codes are simulated only under code capacity, not with the depth-8 syndrome circuits of Bravyi et al., for which BP+OSD on the circuit-level DEM is the standard decoder. Not included: union-find, belief-matching, BP+LSD (ldpc ships BpLsdDecoder), neural decoders, sliding-window or streaming decoding. There is no quantum-computing claim of any kind: this is a benchmark of classical decoders on classically sampled Clifford data.
Checklist (docs/04 §5). (1) Strongest baselines: correlated MWPM and the exact ILP, with BP iterations and flavour swept. (2) Proxy vs real objective: the minimum-weight objective and the LER are reported side by side, and the ILP is shown not to be an LER ceiling. (3) Feasibility: syndrome-validity of every correction is checked, and BP's invalid fraction is reported. (4) Inherited inputs: OSD inherits BP's soft information, and §5.8 varies the BP flavour. (5) Lossy pre-processing: MWPM's hyperedge decomposition, quantified by correlated MWPM and the ILP on the undecomposed DEM. (6) Simulability: everything is classical. (7) Seeds + CIs + structure-removing controls: 3 noise seeds, Wilson and paired McNemar, a no-decoder control and a random syndrome-consistent correction (LER 0.49–0.51, and 1.000 on BB codes). (8) Equal budgets: the same 50 BP iterations everywhere, plus the ablation. (9) Legality: every correction is checked against its syndrome, and PyMatching's refusal on the BB codes is recorded. (10) Exact solver size and time: §5.9.
cd experiments/37-qec-decoder-benchmark
uv sync # stim, pymatching, ldpc (prebuilt wheel), scipy, qcore
uv run pytest -q # 18 tests: CSS commutation, DEM → (H, L) round trip, ILP vs brute force,
# BP+OSD syndrome validity, MWPM = ILP on its own graph, exhaustive OSD = ILP, --quick smoke
uv run python run.py --quick # 15–25 s
uv run python run.py # ≈ 15 min on a loaded 10-core laptop
uv run python run.py --plots-only # rebuild figures + ler_table.csv from results/results.json
QISKIT_IBM_TOKEN=<key> uv run --with 'qiskit-ibm-runtime>=0.40' python scripts/hardware_run_ibm.py --taus-us 0 --ones-ds 3 5 7 9 11 13 --ones-taus-us 0 2 10 # dry run
QISKIT_IBM_TOKEN=<key> uv run --with 'qiskit-ibm-runtime>=0.40' python scripts/hardware_run_ibm.py ... --submit --no-wait # §5.11 job; --job ID with the same options analyses it
Outputs: results/results.json (all metrics, per-point timing, paired tests, gap-to-ILP, side studies), results/ler_table.csv, results/ler_vs_p_{surface,repetition,bb}.png, results/time_per_shot.png, results/threshold_crossing.png, results/gap_to_ilp.png, results/run.log (progress lines; the duplicated metrics dump printed by write_results was stripped).
- Dennis, Kitaev, Landahl, Preskill. Topological quantum memory. J. Math. Phys. 43, 4452 (2002). arXiv:quant-ph/0110143.
- Fowler, Mariantoni, Martinis, Cleland. Surface codes: towards practical large-scale quantum computation. PRA 86, 032324 (2012). arXiv:1208.0928.
- Fowler. Optimal complexity correction of correlated errors in the surface code. arXiv:1310.0863 (2013).
- Higgott, Gidney. Sparse Blossom: correcting a million errors per core second with minimum-weight matching. arXiv:2303.15933 (PyMatching 2).
- Gidney. Stim: a fast stabilizer circuit simulator. Quantum 5, 497 (2021). arXiv:2103.02202.
- Panteleev, Kalachev. Degenerate quantum LDPC codes with good finite length performance. Quantum 5, 585 (2021). arXiv:1904.02703 (BP+OSD).
- Roffe, White, Burton, Campbell. Decoding across the quantum low-density parity-check code landscape. PRR 2, 043423 (2020). arXiv:2005.07016 (BP+OSD-CS;
ldpcpackage). - Poulin, Chung. On the iterative decoding of sparse quantum codes. QIC 8, 987 (2008). arXiv:0801.1241.
- Iyer, Poulin. Hardness of decoding quantum stabilizer codes. IEEE TIT 61, 5209 (2015). arXiv:1310.3235.
- Bravyi, Cross, Gambetta, Maslov, Rall, Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature 627, 778 (2024). arXiv:2308.07915.
- Google Quantum AI. Suppressing quantum errors by scaling a surface code logical qubit. Nature 614, 676 (2023). arXiv:2207.06431.
- Google Quantum AI and collaborators. Quantum error correction below the surface code threshold. Nature 638, 920 (2025). arXiv:2408.13687.
- deMarti iOlius, Fuentes, Orús, Crespo, Etxezarreta Martinez. Decoding algorithms for surface codes. arXiv:2307.14989 (review).
- Huangfu, Hall. Parallelizing the dual revised simplex method. Math. Prog. Comp. 10, 119 (2018) (HiGHS).
- Higgott. stimbposd (DEM → check-matrix construction used here), github.com/oscarhiggott/stimbposd; Roffe. ldpc v2, github.com/quantumgizmos/ldpc.
- This repository, experiment 11 (
experiments/11-qec-decoding-benchmark): generic tabular ML vs MWPM on the same Stim circuits.