Dist m4ri 0.16.1
Computing distance of a classical or quantum CSS code
Loading...
Searching...
No Matches
Benchmark Suite for dist-m4ri

This directory contains quantum LDPC CSS parity-check matrices (.mtx) and Stim circuit-level fault-tolerance files (.stim) spanning code distances $d = 4$ to $d \le 34$. Detector Error Models (.dem) can be generated on the fly from the .stim circuits with dist_m4ri.py (noise is added to the noiseless templates with add_noise); since version 0.14.0, the binary reduces the full DEM of a circuit exactly (Section 3), so that its distance, the circuit-level distance, is found as fast as that of the DEM with the minority-basis detectors stripped.

Note
The distances in the file names (and in the source patterns below) are the nominal values of the sources, and they are not always correct; the file names are kept unchanged. The distances computed with dist_m4ri are listed in the tables below: an exact value is certified (by CC), and $[d_{\min}, d_{\max}]$ is a bracket from a run which hit the timeout. The values of the Mitten codes and circuits and of the full DEMs of the $X$-basis BB circuits are from the overnight benchmark of dist_m4ri 0.14.0 (128 threads, Section 5), and the brackets of the double-gross and bb_360 circuits from the follow-up runs of 0.14.1 (Section 6); the values marked "(s)" are from shorter runs of earlier versions on the stripped DEMs, and they are provisional. The values of the codes and circuits added on 2026-10-20 (the yarn_* Mitten codes and circuits, the SHYPS circuits, the $Z$-basis uniform-noise BB circuits) and the re-runs of the uniform-noise gross circuit and of the torus circuits (Section 2.6) are from short runs of 0.14.7. The distances of the larger codes of Section 1 (the yarn_* codes with $d \ge 16$, bb_360, and bb_756) are from the branch-and-bound CC search of 0.15.0 (Section 9; those up to $d = 18$ confirmed with the walk of the earlier versions, Section 10.1). The 2bga_* codes and circuits added on 2026-11-05 (Origins, item 5) were only checked in short RW runs of 0.15.2: the distances in their prefixes are the exact values of their source database.

Directory Structure

  • css/: MatrixMarket (.mtx) CSS parity-check matrices (_Hx.mtx, _Hz.mtx) and canonical logical operators (_Lx.mtx, _Lz.mtx for the Mitten codes, including the yarn_* codes of arXiv:2607.28795, and for the 2bga_* codes, which also have logical operators of the minimum weight in .nz files, _wX.nz and _wZ.nz).
  • stim_bb/: Unmodified Bivariate Bicycle (BB), Gross, and Double-Gross .stim circuits from external repositories.
  • stim_mitten/: Mitten code .stim circuits generated via quits with CircuitBuildOptions(get_all_detectors=True) (mitten_*), and from the published hook-free schedules of arXiv:2607.28795 with make_yarn_mitten_circuits.py (yarn_*).
  • stim_shyps/: Unmodified SHYPS code .stim circuits ($Z$-basis memory).
  • stim_2bga/: Unmodified .stim circuits of two two-block group-algebra (2BGA) codes (memory in both bases).
  • stim_torus/: 2D local torus Bivariate Bicycle .stim circuits (d = 14 to 17, noiseless templates).
  • figures/: scaling of dist_m4ri with the number of threads on some of these codes and circuits (Section 4), the time to a minimum-weight codeword in the full DEMs of the circuits (Sections 5 and 8), and the lightest codeword found against time with and without the RW pairs (Section 8).

Origins and References

  1. Bivariate Bicycle (BB), Gross ([[144, 12, 12]]), and Double-Gross ([[288, 12, 18]]) Codes
    • Code Construction: S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, High-threshold and low-overhead fault-tolerant quantum memory, Nature 627, 778–782 (2024), arXiv:2308.07915.
    • Higher-Distance BB Codes ([[360, 12, 24]], [[756, 16, <=34]]) & si1000 Stim Circuits: Copied unmodified from quantumlib/tesseract-decoder (commit e7c762eef24161e304ba6fccb856a05b41f88c39, directory testdata/bivariatebicyclecodes/), associated with A. Beni et al., arXiv:2503.10988. These circuits use the superconducting-inspired si1000 noise model at $p = 0.0001$ with $r = d$ rounds in both $X$ and $Z$ memory bases.
    • Uniform-Noise (uniform_circuit) BB Stim Circuits: Copied unmodified from trmue/relay (commit d185194ba0cb4101ced4340d82b2ee6d42f225f0, directory tests/testdata/bicycle_bivariate/), associated with T. Müller et al., arXiv:2503.11514. These circuits use standard uniform circuit-level depolarizing noise at $p = 0.001$ with $r = d$ rounds in the $X$ and $Z$ memory bases (memory_X, memory_Z; the $Z$-basis circuits were added on 2026-10-20, from the same commit).
  2. Mitten Codes (Non-Abelian Lifted-Product CSS Codes)
    • Code Construction & Stim Circuits: Generated via mkangquantum/quits (commit 0f36b8c5a9b81d6b7be0cef2c81c61b5850c0452); the Mitten codes were introduced in High-rate qLDPC processors, arXiv:2607.28795.
    • Constructed as $1 \times 2$ lifted products $LP(A, B)$ over non-abelian groups $G = C_m \times S_3$ of order $|G| = 6m$, yielding parameters $[[5|G|, |G|, d]]$ with row weight 9 and column weight 3 or 6.
    • Circuits are generated at $p = 0.001$ (ErrorModel(1e-3, 1e-3, 1e-3, 1e-3), basis="Z", CircuitBuildOptions(get_all_detectors=True)) for two syndrome-extraction schedules:
      • custom: depth-12 interleaved mixed $X/Z$ schedule.
      • hef (hook_error_free): depth-24 group-element-layer schedule where each entangling layer is a permutation matching between one check block and one data block.
    • Codes of arXiv:2607.28795 and their hook-free circuits (yarn_*): the check matrices and paired logical bases of processor_codes/ (8 mitten, 6 structured_mitten, and 1 abelian_poly_LP code) of a7b/yarn, the repository of the paper (commit 1b58edd24e19b6b5da6814fd3a74ebb376b6e90f, MIT license), converted from .npy to .mtx (css/yarn_*). The circuits stim_mitten/yarn_*_hookfree_r<d>_{X,Z}.stim are generated by stim_mitten/make_yarn_mitten_circuits.py from the published hook-free syndrome-extraction schedules (hook_free_SE_cycle_schedule.json, for 13 of the codes): each cycle runs the 12 CX layers of the $X$-check round, measures the $X$ checks, and then runs the 12 layers of the $Z$-check round; $r = d$ rounds, memory in the $X$ and $Z$ bases, and the noise of dist_m4ri.add_noise(p=0.001). The DEM of the $X$-basis circuit of $[[150, 30, 10]]$ has exactly the 76,245 distinct error mechanisms of the paper's DEM telescoping-decoder/tests/data/paper_nonab_150_30_10_xyz_p0.001_r10_xinit_L1_hookfree.dem.
  3. 2D Local Torus Bivariate Bicycle Stim Circuits
    • Copied unmodified from tmp/*.stim. These are noiseless syndrome-extraction templates on a 2D torus with Swap/CNOT routing (L3_torus, with CZSWAP gates) for codes with the nominal parameters $[[60, 8, 14]]$, $[[120, 8, 15]]$, $[[200, 16, 16]]$, and $[[200, 8, 17]]$ (from the file names; the code distances have not been verified) in both $X$ and $Z$ bases. When passed to dist_m4ri.compute_dem_distance(circuit=...) or dist_m4ri.add_noise(circuit, p=0.001), uniform circuit-level noise is added on the fly (DEPOLARIZE2 after the two-qubit gates, including CZSWAP since 0.14.0, DEPOLARIZE1 after the one-qubit gates and on idle qubits, and X_ERROR/Z_ERROR at resets and measurements; see the README).
  4. SHYPS Codes (Subsystem Hypergraph Product Simplex Codes)
    • Memory circuits copied unmodified from PhotonicInc/ComputingEfficientlyInQLDPCCodes (commit df815862d22dd02d3c3a7f7266639ac5b7840a91, MIT license, directories src/stim_circuits/shyps_r4_memory_circuits/ and src/stim_circuits/shyps_r5_memory_circuits/, the files ..._one_codeblock_memory_simulation_Z_detectors_circuit_p_0.001.stim), associated with A. J. Malcolm et al., Computing Efficiently in QLDPC Codes, arXiv:2502.07150.
    • One code block of the $[[225, 16, 8]]$ ($r = 4$) and $[[961, 25, 16]]$ ($r = 5$) SHYPS codes: $Z$-basis memory with detectors of the $Z$ type only, $d + 1$ rounds of gauge measurements, and circuit-level noise at $p = 0.001$ (DEPOLARIZE2 after the CX gates, flips at the resets and measurements, no idle noise). The repository has no $X$-basis memory circuits of these codes.
  5. Two-Block Group-Algebra (2BGA) Codes of the Bicycle Race Database
    • Codes and Stim circuits: from gideonlsx/bicycle-race (commit cee978f8b92256a4783b7e0792f0207a542a1b1e), the companion database of G. Lee, Bicycle Race: small two-block codes on the Pareto frontier, arXiv:2610.13880 (2026); its data are licensed under CC BY 4.0.
    • A code $C(a, b)$ over a finite group $G$ (elements $e_0, e_1, \ldots$ numbered as in GAP's Elements(SmallGroup(o, i)), $e_0$ the identity) has $n = 2|G|$ qubits, $H_X = (L(a) \mid R(b))$, and $H_Z = (R(b)^T \mid L(a)^T)$, where $L(a)$ ($R(b)$) has a 1 in row $s g$ ($g s$) and column $g$ for each $s$ in $a$ ($b$). The check matrices were rebuilt with the database's scripts/codes.py (which checks the commutation, $k$, and the database's logical operators of weight $d_X$ and $d_Z$); the comment lines of the files give $a$, $b$, and the database id of each code. The paired logical bases _Lx.mtx, _Lz.mtx ($L_X L_Z^T = I$) were computed here, and _wX.nz, _wZ.nz are the database's logical operators of weight $d_X$ and $d_Z$ (.nz list format, 1-based columns, for finC).
    • Seven codes with check weights 5 to 9 and distances 10 to 23, four of them over non-abelian groups. Their distances are the exact values of the database, from the paper's connected-cluster engine. The database also reports dist-m4ri certificates: of both sectors for 2bga_102_20_10_C51, and for 2bga_120_24_10_C30xC2 and 2bga_288_4_20_C24xS3 by CC from the symmetry roots of a checked automorphism group with two orbits.
    • Circuits (Fig. 3b of the paper, copied unmodified and renamed): $X$- and $Z$-basis memory of 2bga_102_20_10_C51 and 2bga_120_24_10_C30xC2, 10 rounds of a "bare, equivariant, sequential" schedule with one ancilla per check, and the idle-free noise model of Zhao et al. (arXiv:2604.16209, App. B.1) at $p = 0.001$ (DEPOLARIZE1 after the preparations and before the measurements, DEPOLARIZE2 after the CX gates, no idle noise). The header of each file describes the circuit and gives the circuit-level distance 8.

1. CSS Parity-Check and Logical Matrices (benchmark/css/)

Prefix $[[n, k, d]]$ Size ($m \times n$) Construction / Polynomials or Group
bb_72_12_6 $[[72, 12, 6]]$ $36 \times 72$ $\ell=6, m=6$, $A=x^3+y+y^2$, $B=y^3+x+x^2$
bb_90_8_10 $[[90, 8, 10]]$ $45 \times 90$ $\ell=15, m=3$, $A=x^9+y+y^2$, $B=1+x^2+x^7$
bb_108_8_10 $[[108, 8, 10]]$ $54 \times 108$ $\ell=9, m=6$, $A=x^3+y+y^2$, $B=y^3+x+x^2$
gross_144_12_12 $[[144, 12, 12]]$ $72 \times 144$ $\ell=12, m=6$, $A=x^3+y+y^2$, $B=y^3+x+x^2$
double_gross_288_12_18 $[[288, 12, 18]]$ $144 \times 288$ $\ell=12, m=12$, $A=x^3+y^2+y^7$, $B=y^3+x+x^2$
bb_360_12_24 $[[360, 12, 24]]$ $180 \times 360$ $\ell=30, m=6$, $A=x^9+y+y^2$, $B=y^3+x^{25}+x^{26}$
bb_756_16_34 $[[756, 16, \le 34]]$ $378 \times 756$ $\ell=21, m=18, A=x^3+y^{10}+y^{17}, B=y^5+x^3+x^{19}$

| mitten_90_18_6_C3xS3 | $[[90, 18, 6]]$ | $36 \times 90$ | $G = C_3 \times S_3$ ($|G|=18$, seed=2) | | mitten_150_30_8_C5xS3 | $[[150, 30, 8]]$ | $60 \times 150$ | $G = C_5 \times S_3$ ($|G|=30$, seed=2) | | mitten_210_42_8_C7xS3 | $[[210, 42, 6]]$ | $84 \times 210$ | $G = C_7 \times S_3$ ($|G|=42$, seed=2) | | mitten_270_54_10_C9xS3 | $[[270, 54, 10]]$ | $108 \times 270$ | $G = C_9 \times S_3$ ($|G|=54$, seed=2) | | mitten_330_66_6_C11xS3 | $[[330, 66, 4]]$ | $132 \times 330$ | $G = C_{11}\times S_3$ ($|G|=66$, seed=2) | | yarn_mitten_150_30_10 | $[[150, 30, 10]]$ | $60 \times 150$ | $G = C_5 \times S_3$ | | yarn_mitten_200_40_12 | $[[200, 40, 12]]$ | $80 \times 200$ | $G = C_4 \times D_{10}$ | | yarn_mitten_300_60_14 | $[[300, 60, 14]]$ | $120 \times 300$ | $G = C_{10} \times S_3$ | | yarn_mitten_500_100_16 | $[[500, 100, 16]]$ | $200 \times 500$ | $G = C_5 \times (C_5 \rtimes C_4)$ | | yarn_mitten_540_108_18 | $[[540, 108, 18]]$ | $216 \times 540$ | $G = (C_9 \rtimes C_3) \rtimes C_4$ | | yarn_mitten_630_126_20 | $[[630, 126, 20]]$ | $252 \times 630$ | $G = C_7 \rtimes C_{18}$ | | yarn_mitten_780_156_22 | $[[780, 156, 22]]$ | $312 \times 780$ | $G = C_{13} \times A_4$ | | yarn_mitten_975_195_24 | $[[975, 195, \le 24]]$ | $390 \times 975$ | $G = C_5 \times (C_{13} \rtimes C_3)$ | | yarn_smitten_300_60_9 | $[[300, 60, 10]]$ | $120 \times 300$ | structured, $G = C_{10} \times S_3$ | | yarn_smitten_330_66_12 | $[[330, 66, 12]]$ | $132 \times 330$ | structured, $G = C_{11} \times S_3$ | | yarn_smitten_600_120_14 | $[[600, 120, 14]]$ | $240 \times 600$ | structured, $G = C_5 \times S_4$ | | yarn_smitten_600_120_16 | $[[600, 120, 16]]$ | $240 \times 600$ | structured, $G = C_5 \times S_4$ | | yarn_smitten_840_168_18 | $[[840, 168, 17]]$ | $336 \times 840$ | structured, $G = C_7 \times S_4$ | | yarn_smitten_1200_240_20 | $[[1200, 240, 20]]$ | $480 \times 1200$ | structured, $|G| = 240$ | | yarn_ablp_560_112_14 | $[[560, 112, 14]]$ | $224 \times 560$ | abelian lifted product, $|G| = 112$ | | 2bga_102_20_10_C51 | $[[102, 20, 10]]$ | $51 \times 102$ | 2BGA, $G = C_{51}$, weight 9 = 5 + 4 | | 2bga_120_24_10_C30xC2 | $[[120, 24, 10]]$ | $60 \times 120$ | 2BGA, $G = C_{30} \times C_2$, weight 9 = 5 + 4 | | 2bga_252_16_20_C7xD18 | $[[252, 16, 20]]$ | $126 \times 252$ | 2BGA, $G = C_7 \times D_{18}$, weight 7 = 4 + 3 | | 2bga_288_4_20_C24xS3 | $[[288, 4, 20]]$ | $144 \times 288$ | 2BGA, $G = C_{24} \times S_3$, weight 5 = 3 + 2 | | 2bga_288_8_22_C18xD8 | $[[288, 8, 22]]$ | $144 \times 288$ | 2BGA, $G = C_{18} \times D_8$, weight 6 = 3 + 3 | | 2bga_292_22_23_C146 | $[[292, 22, 23]]$ | $146 \times 292$ | 2BGA, $G = C_{146}$, weight 8 = 4 + 4 | | 2bga_294_24_21_SG147_5 | $[[294, 24, 21]]$ | $147 \times 294$ | 2BGA, $G = C_7^2 \rtimes C_3$, weight 9 = 6 + 3 |

Distances computed with dist_m4ri:

Prefix $d_X$ $d_Z$
bb_72_12_6 6 6
bb_90_8_10 10 10
bb_108_8_10 – 10
gross_144_12_12 12 12
double_gross_288_12_18 18 18
bb_360_12_24 – 24
bb_756_16_34 – [26, 34]
mitten_90_18_6_C3xS3 6 6
mitten_150_30_8_C5xS3 8 8
mitten_210_42_8_C7xS3 6 8
mitten_270_54_10_C9xS3 10 10
mitten_330_66_6_C11xS3 4 6
yarn_mitten_150_30_10 10 10
yarn_mitten_200_40_12 12 12
yarn_mitten_300_60_14 14 14
yarn_mitten_500_100_16 16 16
yarn_mitten_540_108_18 18 18
yarn_mitten_630_126_20 20 20
yarn_mitten_780_156_22 22 22
yarn_mitten_975_195_24 [23, 24] 24
yarn_smitten_300_60_9 10 10
yarn_smitten_330_66_12 12 12
yarn_smitten_600_120_14 14 14
yarn_smitten_600_120_16 16 16
yarn_smitten_840_168_18 17 18
yarn_smitten_1200_240_20 20 20
yarn_ablp_560_112_14 14 14
2bga_102_20_10_C51 $\le 10$ $\le 10$
2bga_120_24_10_C30xC2 $\le 10$ $\le 10$
2bga_252_16_20_C7xD18 $\le 20$ $\le 20$
2bga_288_4_20_C24xS3 $\le 20$ $\le 20$
2bga_288_8_22_C18xD8 $\le 22$ $\le 22$
2bga_292_22_23_C146 $\le 23$ $\le 23$
2bga_294_24_21_SG147_5 $\le 21$ $\le 21$
  • $d_X$ ($d_Z$) is the minimum weight of an $X$-type ($Z$-type) logical operator, i.e., of a vector $c$ with $H_Z c = 0$ ($H_X c = 0$) which is not in the row space of $H_X$ ($H_Z$); $d = \min(d_X, d_Z)$. "–": not computed yet.
  • For the BB codes, $d_X = d_Z$ by the symmetry exchanging the two sectors, so one sector suffices.
  • mitten_330_66_6_C11xS3 has distance 4, not 6: $d_X = 4$ (132 $X$-type logical operators of weight 4 were found, and those checked independently over GF(2) are valid), while $d_Z = 6$.
  • mitten_210_42_8_C7xS3 has distance 6, not 8: $d_X = 6$, while $d_Z = 8$.
  • The Mitten distances are certified by CC (0.14.0: under 0.04 s per sector on 128 threads), and the lightest logical operator found in each run of the 0.12.1 benchmark passed an independent check over GF(2). Numbers of minimum-weight logical operators ($X$ / $Z$, enumerated by CC): 66 / 90 (mitten_90), 180 / 120 (mitten_150), 84 / 42 (mitten_210), 216 / 648 (mitten_270), and 132 / 132 (mitten_330).
  • For bb_360 and bb_756, the published distances are upper bounds (the codewords found by dist_m4ri have the same weights). 0.15.0 certified $d = 24$ for bb_360 in 3.2 min and raised the lower bound of bb_756 from 17 (60 s runs) to 26 in 12 min (Section 9.3).
  • The yarn_* codes (2026-10-20): method=3 of 0.14.7 with a timeout of 20 s per sector on 128 threads. The upper bounds are the nominal distances, except for yarn_smitten_840_168_18. The codes with $d \ge 16$ were certified by 0.15.0 (2026-10-25, method=3 on 128 threads, Section 9.3): from 1 s per sector for yarn_mitten_500_100_16 to 59 min for $d_Z$ of yarn_mitten_975_195_24, whose $d_X$ is in $[23, 24]$ (the round $w = 23$ was not run).
    • yarn_smitten_300_60_9 has distance 10, not 9, certified by CC in both sectors (also by the single-threaded dist_m4ri_old method=2 wmax=9: no codeword of weight at most 9).
    • yarn_smitten_840_168_18 has distance 17, not 18: RW found 7 distinct $X$-type logical operators of weight 17, valid in an independent check over GF(2), and 0.15.0 certified $d_X = 17$ and $d_Z = 18$.
  • The 2bga_* codes (2026-11-05): $\le w$ is the weight of the lightest logical operator found by RW of 0.15.2 (20,000 steps on 16 threads, under 0.1 s per sector), not certified by CC here. In both sectors of every code it is the exact distance of the source database (Origins, item 5; $d_X = d_Z = d$ in the prefix). The .nz files of these codes give the same upper bounds through finC, and the logical bases _Lx.mtx, _Lz.mtx (finL) the same RW results as finG.

2. Stim Circuits (stim_bb/, stim_mitten/, stim_shyps/, stim_torus/, stim_2bga/)

The circuit-level distances are listed in Section 2.6.

2.1 Bivariate Bicycle, Gross, and Double-Gross (benchmark/stim_bb/)

File (benchmark/stim_bb/) Repo Noise $p$ Rounds Basis Source Pattern
bb_72_12_6_si1000_r6_X.stim tesseract si1000 1e-4 6 X r=6,d=6,nkd=[[72,12,6]]
bb_72_12_6_si1000_r6_Z.stim tesseract si1000 1e-4 6 Z r=6,d=6,nkd=[[72,12,6]]
bb_90_8_10_si1000_r10_X.stim tesseract si1000 1e-4 10 X r=10,d=10,nkd=[[90,8,10]]
bb_90_8_10_si1000_r10_Z.stim tesseract si1000 1e-4 10 Z r=10,d=10,nkd=[[90,8,10]]
bb_108_8_10_si1000_r10_X.stim tesseract si1000 1e-4 10 X r=10,d=10,nkd=[[108,8,10]]
bb_108_8_10_si1000_r10_Z.stim tesseract si1000 1e-4 10 Z r=10,d=10,nkd=[[108,8,10]]
gross_144_12_12_si1000_r12_X.stim tesseract si1000 1e-4 12 X r=12,d=12,nkd=[[144,12,12]]
gross_144_12_12_si1000_r12_Z.stim tesseract si1000 1e-4 12 Z r=12,d=12,nkd=[[144,12,12]]
double_gross_288_12_18_si1000_r18_X.stim tesseract si1000 1e-4 18 X r=18,d=18,[[288,12,18]]
double_gross_288_12_18_si1000_r18_Z.stim tesseract si1000 1e-4 18 Z r=18,d=18,[[288,12,18]]
bb_360_12_24_si1000_r24_X.stim tesseract si1000 1e-4 24 X r=24,d=24,nkd=[[360,12,24]]
bb_360_12_24_si1000_r24_Z.stim tesseract si1000 1e-4 24 Z r=24,d=24,nkd=[[360,12,24]]
bb_756_16_34_si1000_r34_X.stim tesseract si1000 1e-4 34 X r=34,d=34,nkd=[[756,16,34]]
bb_756_16_34_si1000_r34_Z.stim tesseract si1000 1e-4 34 Z r=34,d=34,nkd=[[756,16,34]]
bb_72_12_6_uniform_r6_X.stim relay uniform 1e-3 6 X ..._72_12_6_memory_X
gross_144_12_12_uniform_r12_X.stim relay uniform 1e-3 12 X ..._144_12_12_memory_X
double_gross_288_12_18_uniform_r18_X.stim relay uniform 1e-3 18 X ..._288_12_18_memory_X
bb_72_12_6_uniform_r6_Z.stim relay uniform 1e-3 6 Z ..._72_12_6_memory_Z
gross_144_12_12_uniform_r12_Z.stim relay uniform 1e-3 12 Z ..._144_12_12_memory_Z
double_gross_288_12_18_uniform_r18_Z.stim relay uniform 1e-3 18 Z ..._288_12_18_memory_Z

2.2 Mitten Codes (benchmark/stim_mitten/)

File (benchmark/stim_mitten/) Source Schedule Depth $p$ Rounds Basis
mitten_90_18_6_C3xS3_custom_r4_Z.stim quits custom (interleaved) 12 1e-3 4 Z
mitten_90_18_6_C3xS3_hef_r4_Z.stim quits hook_error_free 24 1e-3 4 Z
mitten_150_30_8_C5xS3_custom_r5_Z.stim quits custom (interleaved) 12 1e-3 5 Z
mitten_150_30_8_C5xS3_hef_r5_Z.stim quits hook_error_free 24 1e-3 5 Z
mitten_210_42_8_C7xS3_custom_r4_Z.stim quits custom (interleaved) 12 1e-3 4 Z
mitten_210_42_8_C7xS3_hef_r4_Z.stim quits hook_error_free 24 1e-3 4 Z
mitten_270_54_10_C9xS3_custom_r4_Z.stim quits custom (interleaved) 12 1e-3 4 Z
mitten_270_54_10_C9xS3_hef_r4_Z.stim quits hook_error_free 24 1e-3 4 Z
mitten_330_66_6_C11xS3_custom_r4_Z.stim quits custom (interleaved) 12 1e-3 4 Z
mitten_330_66_6_C11xS3_hef_r4_Z.stim quits hook_error_free 24 1e-3 4 Z

The quits Mitten circuits are $Z$-basis memory experiments, whose logical observables are flipped by $X$-type errors; their circuit-level distance cannot exceed the code's $d_X$, which is 6 for mitten_210 and 4 for mitten_330 (Section 1).

The circuits of the codes of arXiv:2607.28795 with the published hook-free schedule (Origins, item 2) are generated by make_yarn_mitten_circuits.py in this directory: memory in both bases, $r = d$ rounds (the cycles after the first in a REPEAT block), the noise of dist_m4ri.add_noise(p=0.001); the qubits are the $n$ data qubits and one ancilla per check.

Files (benchmark/stim_mitten/) Code Rounds Qubits Detectors Observables
yarn_mitten_150_30_10_hookfree_r10_{X,Z}.stim $[[150, 30, 10]]$ 10 270 1,200 30
yarn_mitten_200_40_12_hookfree_r12_{X,Z}.stim $[[200, 40, 12]]$ 12 360 1,920 40
yarn_mitten_300_60_14_hookfree_r14_{X,Z}.stim $[[300, 60, 14]]$ 14 540 3,360 60
yarn_mitten_500_100_16_hookfree_r16_{X,Z}.stim $[[500, 100, 16]]$ 16 900 6,400 100
yarn_mitten_540_108_18_hookfree_r18_{X,Z}.stim $[[540, 108, 18]]$ 18 972 7,776 108
yarn_mitten_630_126_20_hookfree_r20_{X,Z}.stim $[[630, 126, 20]]$ 20 1,134 10,080 126
yarn_mitten_780_156_22_hookfree_r22_{X,Z}.stim $[[780, 156, 22]]$ 22 1,404 13,728 156
yarn_mitten_975_195_24_hookfree_r24_{X,Z}.stim $[[975, 195, 24]]$ 24 1,755 18,720 195
yarn_smitten_300_60_9_hookfree_r9_{X,Z}.stim $[[300, 60, 9]]$ 9 540 2,160 60
yarn_smitten_330_66_12_hookfree_r12_{X,Z}.stim $[[330, 66, 12]]$ 12 594 3,168 66
yarn_smitten_600_120_14_hookfree_r14_{X,Z}.stim $[[600, 120, 14]]$ 14 1,080 6,720 120
yarn_smitten_600_120_16_hookfree_r16_{X,Z}.stim $[[600, 120, 16]]$ 16 1,080 7,680 120
yarn_smitten_840_168_18_hookfree_r18_{X,Z}.stim $[[840, 168, 18]]$ 18 1,512 12,096 168

The code parameters are the nominal ones (Section 1 for the distances); the codes yarn_smitten_1200_240_20 and yarn_ablp_560_112_14 have no published schedule.

2.3 2D Local Torus BB Circuits (benchmark/stim_torus/)

File (benchmark/stim_torus/) Nominal $[[n, k, d]]$ Basis Notes
NNEESEEESEENN_L3_torus_s1_NW_w10p_s2_SW_w6p_n60_k8_d14_X.stim $[[60, 8, 14]]$ X Noiseless (tmp/)
NNEESEEESEENN_L3_torus_s1_NW_w10p_s2_SW_w6p_n60_k8_d14_Z.stim $[[60, 8, 14]]$ Z Noiseless (tmp/)
NEENNWNWNNEEN_L3_torus_s1_NW_w10p_s2_SW_w12p_n120_k8_d15_X.stim $[[120, 8, 15]]$ X Noiseless (tmp/)
NEENNWNWNNEEN_L3_torus_s1_NW_w10p_s2_SW_w12p_n120_k8_d15_Z.stim $[[120, 8, 15]]$ Z Noiseless (tmp/)
NEENNWNWNNEEN_L3_torus_s1_NW_w10p_s2_SW_w20p_n200_k16_d16_X.stim $[[200, 16, 16]]$ X Noiseless (tmp/)
NEENNWNWNNEEN_L3_torus_s1_NW_w10p_s2_SW_w20p_n200_k16_d16_Z.stim $[[200, 16, 16]]$ Z Noiseless (tmp/)
ENENESESENENE_L3_torus_s1_NW_w10p_s2_SW_w20p_n200_k8_d17_X.stim $[[200, 8, 17]]$ X Noiseless (tmp/)
ENENESESENENE_L3_torus_s1_NW_w10p_s2_SW_w20p_n200_k8_d17_Z.stim $[[200, 8, 17]]$ Z Noiseless (tmp/)

The nominal code parameters are taken from the file names; the code distances of the torus codes have not been verified yet (no check matrices are included).

2.4 SHYPS Codes (benchmark/stim_shyps/)

File (benchmark/stim_shyps/) Code $r$ Rounds Basis Source file
shyps_225_16_8_r9_Z.stim $[[225, 16, 8]]$ 4 9 Z shyps_r4_..._Z_detectors_circuit_p_0.001.stim
shyps_961_25_16_r17_Z.stim $[[961, 25, 16]]$ 5 17 Z shyps_r5_..._Z_detectors_circuit_p_0.001.stim

SHYPS codes are subsystem codes: each round measures the $Z$- and the $X$-type gauge operators, and the circuits have detectors of the $Z$ type only (Origins, item 4).

2.5 2BGA Codes (benchmark/stim_2bga/)

File (benchmark/stim_2bga/) Code Rounds Qubits Detectors Observables Basis
2bga_102_20_10_C51_idlefree_r10_X.stim $[[102, 20, 10]]$ 10 204 561 20 X
2bga_102_20_10_C51_idlefree_r10_Z.stim $[[102, 20, 10]]$ 10 204 561 20 Z
2bga_120_24_10_C30xC2_idlefree_r10_X.stim $[[120, 24, 10]]$ 10 240 660 24 X
2bga_120_24_10_C30xC2_idlefree_r10_Z.stim $[[120, 24, 10]]$ 10 240 660 24 Z

The source files are w9_102_20_10_g51_1_2859_memory_{x,z}basis_r10_idlefree_p0.001.stim and w9t_120_24_10_g60_13_48f7b6_memory_{x,z}basis_r10_idlefree_p0.001.stim in data/circuits/ of the database (Origins, item 5). The qubits are numbered as in the database: data qubit $j < |G|$ in the left block and $|G| + j$ in the right block, and the ancilla of check $i$ (row $i$ of _Hx.mtx or _Hz.mtx in css/) is $n + i$ for an $X$ check and $n + |G| + i$ for a $Z$ check; in the first round, the CX gates of every ancilla address exactly the support of its check. Each circuit has the detectors of its own basis only; the full DEM has 8,262 (2bga_102) or 9,720 (2bga_120) error mechanisms.

2.6 Circuit-Level Distances

The circuit-level distance is the minimum number of faults (error mechanisms of the DEM) which cause an undetectable logical error, i.e., the distance of the full DEM (all detectors).

  • Values without a mark: the full DEM, computed by dist_m4ri 0.14.0 in the overnight benchmark (Section 5; method=3, 128 threads), which drops the minority-basis detectors exactly (Section 3). An exact value is certified by CC: in under 6 s, except 179 s for gross and 182 s for mitten_270 custom.
  • The brackets of double_gross and bb_360 are from Section 6: the lower bounds are certified with a code-sized model of the circuit (Section 6.3), and the upper bounds are codewords of the full DEM found by RW (Sections 6.1, 6.2).
  • The uniform-noise gross circuit and the torus circuits were re-run on their full DEMs with the current noise on 2026-10-15, and the yarn_mitten_150 circuits, the $Z$-basis bb_72 uniform-noise circuit, and shyps_225 on 2026-10-20 (method=3 of 0.14.7, default threads): all values certified by CC, in 0.4–168 s, and in 114 s ($X$) and 291 s ($Z$) for yarn_mitten_150 and 20 s for shyps_225.
  • (s): the stripped DEM (minority-basis detectors removed), computed by earlier versions in 30 s method=3 runs on 16 threads. The stripped DEM keeps a subset of the detectors, so its distance is a lower bound on the circuit distance (for a bracket, only its lower end applies to the circuit).
  • For the noiseless torus templates, the noise of add_noise(p=0.001) is added; the circuit distance depends on the noise model (which faults are included), but not on $p$. Since 0.14.0, add_noise also adds DEPOLARIZE2 after CZSWAP, which these circuits use for routing; the torus values are for this noise.
  • $\le w$ (the 2bga_* circuits, 2026-11-05): the weight of the lightest logical error found by RW of 0.15.2 in the full DEM of the circuit with its own noise (8 s on 16 threads), not certified; it is the circuit-level distance 8 given in the headers of the files (Section 2.5).
  • "–": not computed yet; "n/a": no circuit for this basis.
Circuit (.stim file name without _X/_Z) $X$ basis $Z$ basis
bb_72_12_6_si1000_r6 6 6 (s)
bb_90_8_10_si1000_r10 8 –
bb_108_8_10_si1000_r10 8 –
gross_144_12_12_si1000_r12 10 –
double_gross_288_12_18_si1000_r18 [12, 18] –
bb_360_12_24_si1000_r24 [12, 23] –
bb_756_16_34_si1000_r34 – –
bb_72_12_6_uniform_r6 6 (s) 6
gross_144_12_12_uniform_r12 10 –
double_gross_288_12_18_uniform_r18 – –
mitten_90_18_6_C3xS3_custom_r4 n/a 5
mitten_90_18_6_C3xS3_hef_r4 n/a 4
mitten_150_30_8_C5xS3_custom_r5 n/a 7
mitten_150_30_8_C5xS3_hef_r5 n/a 5
mitten_210_42_8_C7xS3_custom_r4 n/a 6
mitten_210_42_8_C7xS3_hef_r4 n/a 5
mitten_270_54_10_C9xS3_custom_r4 n/a 9
mitten_270_54_10_C9xS3_hef_r4 n/a 7
mitten_330_66_6_C11xS3_custom_r4 n/a 4
mitten_330_66_6_C11xS3_hef_r4 n/a 4
yarn_mitten_150_30_10_hookfree_r10 8 8
yarn_mitten_*, yarn_smitten_* (the other 12 codes, Section 2.2) – –
shyps_225_16_8_r9 n/a 8
shyps_961_25_16_r17 n/a –
NNEESEEESEENN_L3_torus_..._n60_k8_d14 6 6
NEENNWNWNNEEN_L3_torus_..._n120_k8_d15 6 –
NEENNWNWNNEEN_L3_torus_..._n200_k16_d16 8 –
ENENESESENENE_L3_torus_..._n200_k8_d17 8 –
2bga_102_20_10_C51_idlefree_r10 $\le 8$ $\le 8$
2bga_120_24_10_C30xC2_idlefree_r10 $\le 8$ $\le 8$

The circuit-level distances are often below the code distances in the file names. For example, the gross-code circuit has distance 10 (also with the uniform noise), consistent with the circuit-level distance $\le 10$ reported for the IBM syndrome-extraction circuit, and the BB circuits with $d = 10$ have distance 8. For the Mitten codes, the "hook-error-free" schedule of quits has a lower circuit-level distance than the custom schedule (4 vs 5, 5 vs 7, 5 vs 6, and 7 vs 9 for mitten_90, mitten_150, mitten_210, and mitten_270; 4 with both schedules for mitten_330). The custom schedule reaches the code's $d_X$ for mitten_210 (6) and mitten_330 (4), and $d_X - 1$ for mitten_90, mitten_150, and mitten_270. With the published hook-free schedule, the circuit-level distance of yarn_mitten_150_30_10 is 8 in both bases, two below the code distance 10; the paper's DEM of this circuit (Origins, item 2) has the same error mechanisms, and RW finds 117 distinct logical errors of weight 8 in it. A weight-8 logical error of the $X$-basis circuit consists of four hook errors on $Z$-check ancillas in the last cycle ($Z$ errors which spread to the data qubits of the later CX gates of their checks) and four single data-qubit $Z$ errors. The SHYPS circuit shyps_225_16_8_r9_Z keeps the code distance 8.

3. Full DEMs and Their Exact Reduction

In circuit-level noise models using DEPOLARIZE2(p), cross-term two-qubit Pauli errors (such as $X \otimes Z$, $Y \otimes X$, $Y \otimes Z$, $Y \otimes Y$) occur with probability $p/15 = O(p)$, the same order as single-type errors ($X \otimes X$ or $Z \otimes Z$). Consequently, the full DEM couples $X$-detectors and $Z$-detectors into a single large parity-check matrix with 6–8 times more distinct error columns than a single-basis projection. Since version 0.14.0, dist_m4ri merges the equal columns of a DEM and drops detectors when this is verified to be exact (drop=auto, the default; see "Dropping DEM Detectors" in the README): for every circuit below with detectors of both bases (all but the SHYPS circuits, whose detectors are all of the $Z$ type), it finds exactly the minority-basis detectors, and the matrix searched is the stripped DEM with its equal columns merged (the search for the detectors to drop takes 0.02–0.4 s, and 1.2 s for bb_756, with 0.14.0). Hence the distance of the full DEM, the circuit-level distance, is found as fast as that of the stripped DEM, which is only a lower bound on it.

To avoid storing large pre-generated .dem files in the repository, DEMs can be generated on the fly from the .stim files (noise of strength p_noise=0.001 is added to the noiseless templates; --force-noise replaces the noise of a circuit by this uniform noise):

import dist_m4ri
# the full DEM of the circuit, reduced exactly by the binary; also save the reduced DEM and its maps to the full one
dist, bounds = dist_m4ri.compute_dem_distance(
circuit="benchmark/stim_torus/NNEESEEESEENN_L3_torus_s1_NW_w10p_s2_SW_w6p_n60_k8_d14_X.stim",
out_dem="tmp/torus_n60_X_full.dem", out_reduced="tmp/torus_n60_X") # tmp/torus_n60_X_red.dem, _red.json
dist_m4ri.compute_dem_distance
Tuple[Any,...] compute_dem_distance(Optional[Any] dem=None, Optional[Any] circuit=None, Optional[str] dist_m4ri=None, int method=3, Optional[int] threads=None, float timeout=60.0, Optional[int] num_steps=None, int d_exp=0, int d_min=0, int d_max=0, int dmin=0, int dmax=0, int dstop=0, int wmin=1, int wmax=0, Optional[int] smax=None, Optional[Union[int, str, Sequence[int]]] start=None, Optional[int] cbeg=None, Optional[int] cend=None, int noscan=0, int dW=-1, int maxC=0, float pmin=0.0, bool merge=True, bool expand=False, Optional[Union[bool, int, str, Path]] drop=None, Optional[Union[str, Path]] outD=None, Optional[Union[bool, str, Path]] out_reduced=None, Optional[str] finC=None, Optional[str] outC=None, bool do_cws=False, Optional[Union[str, Path]] cache_file=None, str solver="dist_m4ri", str codedistance_method="UndetectableErrorStim", Optional[Dict[str, Any]] codedistance_params=None, int seed=0, int debug=0, bool verbose=False, bool nothrottle=False, int chunk_size=0, int ksub=0, int kwin=0, int win_mode=0, int win_hyb=0, int pairs=-1, Optional[int] min_hits=None, int cov_cws=100, Optional[int] refresh=None, Optional[bool] simple=None, Optional[bool] full=None, Optional[str] basis=None, Optional[int] rounds=None, Optional[Union[str, Path]] out_dir=None, Optional[Union[bool, str, Path]] out_dem=None, Optional[Union[bool, str, Path]] out_stim=None, float p_noise=0.001, bool force_noise=False, bool trust_start=False, bool start_scan=False, Optional[bool] sort_rows=None, Optional[int] cc_prune=None, Optional[str] engine=None, **kwargs)
Definition dist_m4ri.py:5317
Stim circuit Basis Full (dets x errs) Stripped Searched $k$
mitten_90_18_6_C3xS3_custom_r4_Z Z 360 x 23,394 216 x 3,330 216 x 2,970 18
mitten_90_18_6_C3xS3_hef_r4_Z Z 360 x 22,410 216 x 3,330 216 x 2,970 18
mitten_150_30_8_C5xS3_custom_r5_Z Z 720 x 47,700 420 x 6,660 420 x 5,910 30
mitten_150_30_8_C5xS3_hef_r5_Z Z 720 x 46,130 420 x 6,660 420 x 5,910 30
mitten_210_42_8_C7xS3_custom_r4_Z Z 840 x 54,726 504 x 7,770 504 x 6,930 42
mitten_210_42_8_C7xS3_hef_r4_Z Z 840 x 52,437 504 x 7,665 504 x 6,825 42
mitten_270_54_10_C9xS3_custom_r4_Z Z 1,080 x 70,254 648 x 9,990 648 x 8,910 54
mitten_270_54_10_C9xS3_hef_r4_Z Z 1,080 x 67,482 648 x 9,990 648 x 8,910 54
mitten_330_66_6_C11xS3_custom_r4_Z Z 1,320 x 85,932 792 x 12,210 792 x 10,890 66
mitten_330_66_6_C11xS3_hef_r4_Z Z 1,320 x 81,642 792 x 11,880 792 x 10,560 66
bb_72_12_6_si1000_r6_X X 432 x 17,280 252 x 2,664 252 x 2,232 12
bb_72_12_6_si1000_r6_Z Z 432 x 17,244 252 x 2,664 252 x 2,232 12
bb_90_8_10_si1000_r10_X X 900 x 37,440 495 x 5,490 495 x 4,590 8
bb_90_8_10_si1000_r10_Z Z 900 x 37,395 495 x 5,490 495 x 4,590 8
bb_108_8_10_si1000_r10_X X 1,080 x 44,928 594 x 6,588 594 x 5,508 8
bb_108_8_10_si1000_r10_Z Z 1,080 x 44,874 594 x 6,588 594 x 5,508 8
gross_144_12_12_si1000_r12_X X 1,728 x 72,576 936 x 10,512 936 x 8,784 12
gross_144_12_12_si1000_r12_Z Z 1,728 x 72,504 936 x 10,512 936 x 8,784 12
double_gross_288_12_18_si1000_r18_X X 5,184 x 221,184 2,736 x 31,392 2,736 x 26,208 12
double_gross_288_12_18_si1000_r18_Z Z 5,184 x 221,040 2,736 x 31,392 2,736 x 26,208 12
bb_360_12_24_si1000_r24_X X 8,640 x 371,520 4,500 x 52,200 4,500 x 43,560 12
bb_360_12_24_si1000_r24_Z Z 8,640 x 371,340 4,500 x 52,200 4,500 x 43,560 12
bb_756_16_34_si1000_r34_X X 25,704 x 1,112,832 13,230 x 154,980 13,230 x 129,276 16
bb_756_16_34_si1000_r34_Z Z 25,704 x 1,112,454 13,230 x 154,980 13,230 x 129,276 16
bb_72_12_6_uniform_r6_X X 432 x 16,200 252 x 2,232 252 x 2,232 12
gross_144_12_12_uniform_r12_X X 1,728 x 67,824 936 x 8,784 936 x 8,784 12
double_gross_288_12_18_uniform_r18_X X 5,184 x 206,496 2,736 x 26,208 2,736 x 26,208 12
bb_72_12_6_uniform_r6_Z Z 432 x 16,164 252 x 2,232 252 x 2,232 12
gross_144_12_12_uniform_r12_Z Z 1,728 x 67,752 936 x 8,784 936 x 8,784 12
double_gross_288_12_18_uniform_r18_Z Z 5,184 x 206,352 2,736 x 26,208 2,736 x 26,208 12
yarn_mitten_150_30_10_hookfree_r10_X X 1,200 x 80,295 660 x 11,100 660 x 9,600 30
yarn_mitten_150_30_10_hookfree_r10_Z Z 1,200 x 80,445 660 x 11,250 660 x 9,750 30
yarn_mitten_200_40_12_hookfree_r12 X, Z 1,920 x 130,392 1,040 x 17,960 1,040 x 15,560 40
yarn_mitten_300_60_14_hookfree_r14_X X 3,360 x 230,010 1,800 x 31,380 1,800 x 27,180 60
yarn_mitten_300_60_14_hookfree_r14_Z Z 3,360 x 230,040 1,800 x 31,380 1,800 x 27,180 60
yarn_mitten_500_100_16_hookfree_r16_X X 6,400 x 440,800 3,400 x 59,700 3,400 x 51,700 100
yarn_mitten_500_100_16_hookfree_r16_Z Z 6,400 x 440,780 3,400 x 59,700 3,400 x 51,700 100
yarn_mitten_540_108_18_hookfree_r18_X X 7,776 x 538,056 4,104 x 72,468 4,104 x 62,748 108
yarn_mitten_540_108_18_hookfree_r18_Z Z 7,776 x 538,026 4,104 x 72,468 4,104 x 62,748 108
yarn_mitten_630_126_20_hookfree_r20 X, Z 10,080 x 700,056 5,292 x 93,870 5,292 x 81,270 126
yarn_mitten_780_156_22_hookfree_r22 X, Z 13,728 x 956,280 7,176 x 127,764 7,176 x 110,604 156
yarn_mitten_975_195_24_hookfree_r24 X, Z 18,720 x 1,307,265 9,750 x 174,135 9,750 x 150,735 195
yarn_smitten_300_60_9_hookfree_r9 X, Z 2,160 x 143,940 1,200 x 20,280 1,200 x 17,580 60
yarn_smitten_330_66_12_hookfree_r12 X, Z 3,168 x 215,160 1,716 x 29,634 1,716 x 25,674 66
yarn_smitten_600_120_14_hookfree_r14 X, Z 6,720 x 460,080 3,600 x 62,760 3,600 x 54,360 120
yarn_smitten_600_120_16_hookfree_r16 X, Z 7,680 x 528,960 4,080 x 71,640 4,080 x 62,040 120
yarn_smitten_840_168_18_hookfree_r18 X, Z 12,096 x 836,976 6,384 x 112,728 6,384 x 97,608 168
shyps_225_16_8_r9_Z Z 600 x 10,125 600 x 10,125 600 x 8,325 16
shyps_961_25_16_r17_Z Z 3,596 x 81,685 3,596 x 81,685 3,596 x 66,309 25
NNEESEEESEENN_..._n60_k8_d14_X X 120 x 10,710 90 x 1,500 90 x 1,500 8
NNEESEEESEENN_..._n60_k8_d14_Z Z 120 x 10,710 90 x 1,500 90 x 1,500 8
NEENNWNWNNEEN_..._n120_k8_d15_X X 240 x 21,120 180 x 3,000 180 x 3,000 8
NEENNWNWNNEEN_..._n120_k8_d15_Z Z 240 x 21,120 180 x 3,000 180 x 3,000 8
NEENNWNWNNEEN_..._n200_k16_d16_X X 400 x 35,200 300 x 5,000 300 x 5,000 16
NEENNWNWNNEEN_..._n200_k16_d16_Z Z 400 x 35,200 300 x 5,000 300 x 5,000 16
ENENESESENENE_..._n200_k8_d17_X X 400 x 29,200 300 x 4,800 300 x 4,800 8
ENENESESENENE_..._n200_k8_d17_Z Z 400 x 29,200 300 x 4,800 300 x 4,800 8

The sizes are those of the DEMs generated by dist_m4ri.py 0.14.0 (stim 1.16; the torus templates with the noise of add_noise, which since 0.14.0 includes DEPOLARIZE2 after CZSWAP: their full DEMs have about twice as many columns as with the noise of the earlier versions, and the same stripped DEMs). The full DEMs of the si1000 and Mitten circuits have 5–7% equal columns, and their stripped DEMs 11–16% (merged by the binary); the DEMs of the uniform-noise circuits and of the torus templates have none. The rows of the circuits added on 2026-10-20 are from dist_m4ri.py 0.14.7 (the same DEM generation and reduction): the full DEMs of the yarn_* circuits have 5% equal columns (stim does not merge the equal errors of different repetitions of a REPEAT block) and their stripped DEMs 13–14%; the SHYPS DEMs have 18–19%, and no detector is dropped.

4. Scaling with the Number of Threads (benchmark/figures/)

Wall time and speedup $T(1)/T(p)$ of dist_m4ri for $p = 1, \dots, 128$ threads on a two-socket AMD EPYC 7B13 server (2 x 32 cores, 128 logical CPUs with SMT, 236 GB of memory), with nothrottle=1, threads=p, and taskset to the logical CPUs $0..p-1$ (socket 0 first, then socket 1, then the SMT siblings for $p > 64$; the gray line marks $p = 64$, one thread per physical core). Each run does a fixed amount of work: method=1 a fixed number of RW steps with min_hits=0, method=2 all CC rounds up to wmax, and method=3 both (or, with the default parameters, the search for the exact distance). Versions: 0.15.2 (2026-10-28, scratch/bench_0.15.2_scaling/) and those of Section 5: 0.14.0, 0.12.2, 0.9.0 (pull request #26), and the legacy single-threaded dist_m4ri_old (one thread; built from the 0.14.0 sources, so that it shares the input stage, e.g., the merging of equal columns and the dropping of detectors of a DEM). The runs of 0.9.0 were limited to 600 s per case and method (both older versions: 400 s on the full DEM), from many threads to few, so that some of the runs with few threads are missing; an open marker is a run stopped at the wall-clock limit. The times include reading the input (median of repeated runs for the fast cases). Since 0.14.4, an RW step also checks pairs of non-pivot columns (Section 8): a fixed number of steps takes 1.2–1.6 times longer with 0.15.2 than with 0.14.0, but far fewer steps are needed to find a light codeword. The text below gives the times of 0.14.0, then (from "0.15.2:" on) those of 0.15.2.

Scaling for the gross code

gross $[[144, 12, 12]]$, one sector (css/gross_144_12_12_Hx.mtx with _Hz.mtx; method=1: steps=3000000, method=2: wmax=11, method=3: default parameters). RW takes 50 s on one thread (as in 0.12.2; 0.9.0: 96 s) and scales almost linearly up to 64 threads (58x); the SMT siblings add another 40% (80x at 128 threads). CC up to $w = 11$ takes 0.067 s on one thread, 3.3x less than 0.12.2 and 75x less than 0.9.0; beyond 8–16 threads, the run (15–25 ms) is limited by the start-up of the threads. 0.15.2: RW 76 s on one thread (the pairs; the same scaling), CC as with 0.14.0 (0.067 s), and method=3 0.093 s on one thread instead of 0.16 s.

Scaling for the double-gross code

double-gross $[[288, 12, 18]]$, one sector (steps=1000000; wmax=15; steps=500000 wmax=15). RW scales to 80x at 128 threads (55 s on one thread; 0.9.0: 127 s). CC up to $w = 15$ takes 10 s on one thread, 3.9x less than 0.12.2 (the last cluster extension is now looked up in a hash table), and 0.16 s on 128 threads (speedup 62); 0.9.0 needs 472 s for this CC run on 128 threads. method=3: 0.46 s on 128 threads (0.12.2: 0.75 s; 0.9.0: 551 s). 0.15.2: CC up to $w = 15$ takes 3.1 s on one thread, 3.2x less than 0.14.0 (the branch and bound, Section 9), and 0.072 s on 128 threads; RW 79 s on one thread (the pairs); method=3 (500000 steps) 43 s on one thread, as 0.14.0, and 0.63 s on 128 threads.

Scaling for the double-gross circuit DEM

double-gross circuit (stim_bb/double_gross_288_12_18_si1000_r18_X.stim, stripped DEM $2736 \times 31392$, merged to 26208 columns by 0.14.0; steps=300; wmax=5; steps=150 wmax=5). RW takes 20.7 s on one thread, 2.8x less than 0.12.2 (1.2x from merging the equal columns, 2.3x from the faster RW elimination on large matrices); on this large matrix it is limited by the memory bandwidth (dense copies of $H$ and $H^T$ per thread), at most about 15–20x, at 64 threads on both sockets, and the SMT siblings of socket 0 ($p = 96$) make it slower. CC up to $w = 5$ takes 0.61 s on one thread, 21x less than 0.12.2 (1.8x from merging, 11x from the faster CC), and 0.12–0.15 s from 16 threads on. 0.15.2: RW 25 s on one thread (the pairs), at most 11x faster on many threads (0.14.0: 18x); CC up to $w = 5$ 0.80 s on one thread (0.63 s with cc_prune=0: on such small rounds the walk is faster than the branch and bound) and 0.13–0.20 s from 16 threads on.

Scaling for the full DEM of the bb_72 circuit

bb_72 circuit, full DEM (stim_bb/bb_72_12_6_si1000_r6_X.stim, $432 \times 17280$; steps=20000; wmax=5; default parameters, i.e., the exact distance 6). 0.14.0 reduces the full DEM exactly to $252 \times 2232$ (the stripped DEM, merged): RW takes 5.6 s on one thread instead of 99 s (0.12.2) and 163 s (0.9.0, two threads), and 0.18 s on 128 threads instead of 2.1 s and 7.2 s. CC up to $w = 5$ takes 0.11 s on one thread, against 176 s for 0.12.2 on four threads and more than 400 s for 0.9.0 on 128 threads; on 128 threads, 0.088 s against 9.8 s for 0.12.2 (112x). The reduced problem is so small that more threads hardly help CC (0.08–0.11 s); the exact distance takes 0.09–0.24 s. 0.15.2: RW 8.9 s on one thread (the pairs) and 0.27 s on 128 threads; CC as with 0.14.0 (0.12 s on one thread, 0.10 s on 128), the exact distance 0.34 s on one thread and 0.12 s on 128.

5. Overnight Benchmark of 0.14.0 (2026-10-11)

Versions: 0.14.0 (commit 40faf58), 0.12.2 (528f35f, the version of the previous benchmark), and 0.9.0 (1f46277, pull request #26, 2026-09-18), on the server of Section 4. All versions read the same DEM files (the components of decomposed errors summed mod 2, so that the older DEM readers read the same matrices), identical to the inputs of the previous benchmark of 0.12.1; 1547 runs in 7 h, plus 40 runs of the ablation (Section 5.5). The scaling runs are in Section 4.

5.1 Certified circuit distances (0.14.0, full DEMs, method=3, 128 threads)

Circuit full DEM searched $d$ time (s) 0.12.1: stripped DEM
mitten_90_18_6_C3xS3_custom_r4_Z 360 x 23394 216 x 2970 5 0.18 5 in 0.06 s
mitten_90_18_6_C3xS3_hef_r4_Z 360 x 22410 216 x 2970 4 0.18 4 in 0.05 s
mitten_150_30_8_C5xS3_custom_r5_Z 720 x 47700 420 x 5910 7 0.56 7 in 8.0 s
mitten_150_30_8_C5xS3_hef_r5_Z 720 x 46130 420 x 5910 5 0.40 5 in 0.15 s
mitten_210_42_8_C7xS3_custom_r4_Z 840 x 54726 504 x 6930 6 0.48 6 in 0.48 s
mitten_210_42_8_C7xS3_hef_r4_Z 840 x 52437 504 x 6825 5 0.50 5 in 0.17 s
mitten_270_54_10_C9xS3_custom_r4_Z 1080 x 70254 648 x 8910 9 182 9 in 7700 s
mitten_270_54_10_C9xS3_hef_r4_Z 1080 x 67482 648 x 8910 7 5.8 7 in 184 s
mitten_330_66_6_C11xS3_custom_r4_Z 1320 x 85932 792 x 10890 4 0.70 4 in 0.22 s
mitten_330_66_6_C11xS3_hef_r4_Z 1320 x 81642 792 x 10560 4 0.76 4 in 0.21 s
bb_72_12_6_si1000_r6_X 432 x 17280 252 x 2232 6 0.11
bb_90_8_10_si1000_r10_X 900 x 37440 495 x 4590 8 0.68
bb_108_8_10_si1000_r10_X 1080 x 44928 594 x 5508 8 0.71
gross_144_12_12_si1000_r12_X 1728 x 72576 936 x 8784 10 179
double_gross_288_12_18_si1000_r18_X 5184 x 221184 2736 x 26208 [11, 19] 10211
NNEESEEESEENN_..._n60_k8_d14_X 120 x 10710 90 x 1500 6 0.15
  • All ten Mitten distances are now certified on the full DEMs. mitten_270 custom took 182 s, against 7700 s for the stripped DEM with 0.12.1, when its full DEM could not be certified at all (CC on its 70254 columns did not close the bracket $[9, 10]$ in 2.8 h).
  • The double-gross circuit: CC certified $d_{\min} = 11$ (all rounds up to $w = 10$) and RW found a codeword of weight 19; the run ended at 2.8 h, since the CC round $w = 11$ was predicted not to finish in the time left. The earlier brackets were $[4, 24]$ for the stripped DEM and $[4, 53]$ for the full one. Section 6 improves the bracket to $[12, 18]$.

5.2 Full DEMs: time to a codeword of the minimum weight

The time of RW (method=1, wmin=d: the run stops at the first codeword of weight at most $d$; 128 threads, nothrottle=1, timeout 300 s) on the full DEMs: 0.14.0 reduces them exactly, the older versions work on the full matrices. "> 300 (w)": no codeword of weight $d$ found, $w$ is the lightest weight found. The figure of Section 8.1 shows these times together with those of 0.14.3 and 0.14.5.

Circuit $d$ full DEM 0.14.0 0.12.2 0.9.0
bb_72_12_6_si1000_r6_X 6 432 x 17280 0.089 0.13 0.32
mitten_90_18_6_C3xS3_custom_r4_Z 5 360 x 23394 0.16 0.21 0.44
mitten_90_18_6_C3xS3_hef_r4_Z 4 360 x 22410 0.17 0.23 0.44
mitten_150_30_8_C5xS3_custom_r5_Z 7 720 x 47700 0.36 52.3 > 300 (13)
mitten_150_30_8_C5xS3_hef_r5_Z 5 720 x 46130 0.39 0.84 44.8
mitten_210_42_8_C7xS3_custom_r4_Z 6 840 x 54726 0.42 0.84 37.2
mitten_210_42_8_C7xS3_hef_r4_Z 5 840 x 52437 0.47 6.77 8.60
mitten_270_54_10_C9xS3_custom_r4_Z 9 1080 x 70254 1.36 > 300 (10) > 300 (307)
mitten_270_54_10_C9xS3_hef_r4_Z 7 1080 x 67482 1.12 > 300 (8) > 300 (197)
mitten_330_66_6_C11xS3_custom_r4_Z 4 1320 x 85932 0.73 2.11 2.31
mitten_330_66_6_C11xS3_hef_r4_Z 4 1320 x 81642 0.73 2.15 2.10

0.14.0 finds a minimum-weight codeword in at most 1.4 s for all eleven circuits (including reading the DEM and the reduction); 0.12.2 needs up to 52 s and finds none for the two mitten_270 circuits in 300 s, and 0.9.0 misses three. The reduction makes each RW step cheaper (about 8 times fewer columns, and lighter ones) and much more likely to find a codeword of weight $w$: the probability that an information set contains one scales roughly as $(r/n)^{w-1}$ (rank $r$, $n$ columns).

5.3 Default parameters (no threads=, throttling on, no taskset)

Wall time in s (median of the repeated runs for the fast cases); the arguments are those of the scaling runs (Section 4).

case method 0.14.0 0.12.2 0.9.0
QX150 $[[150,32,6]]$, one sector 1 0.54 0.53 21.3
2 0.006 0.006 0.006
3 0.017 0.017 0.012
c204H $[204,102,8]$ 1 0.49 0.46 18.8
2 0.007 0.009 0.039
3 0.018 0.018 0.034
bb_72 circuit, stripped DEM 1 0.85 0.92 7.40
2 0.025 0.039 0.29
3 0.053 0.092 0.38
bb_72 circuit, full DEM 1 0.19 2.21 6.69
2 0.095 9.57 > 400
3 0.12 10.3 > 400
gross, one sector 1 0.66 0.65 23.9
2 0.028 0.033 1.15
3 0.031 0.038 1.17
double gross, one sector 1 0.76 0.76 31.9
2 0.16 0.48 1021
3 0.47 0.76 1051
random LDPC, $n = 3000$ 1 0.49 1.13 1.66
2 0.13 0.29 16.2
3 0.40 0.88 4.34
double-gross circuit, stripped DEM 1 1.49 3.65 7.54
2 0.15 0.28 11.9
3 1.45 2.87 30.3

With the default parameters, 0.9.0 uses at most four threads for the small codes (hence the slow RW), and its CC is up to 6000 times slower (double gross: 17 min instead of 0.16 s). Compared with 0.12.2, 0.14.0 has the same RW speed on the small matrices, and it is 2.3–2.5 times faster on the large ones (the LDPC code, the double-gross DEM), 1.2–3 times faster in CC, and 12–100 times faster on the full DEM.

5.4 Large full DEMs (RW for 180 s, default parameters)

DEM version read searched drop=auto (s) RW threads s/step/thread RW steps lightest
gross_144_12_12_si1000_r12_X 0.14.0 1728 x 72576 936 x 8784 0.07 128 0.010 2,216,685 10
gross_144_12_12_si1000_r12_X 0.12.2 1728 x 72576 1728 x 72576 32 0.70 8,223 11
bb_360_12_24_si1000_r24_X 0.14.0 8640 x 371520 4500 x 43560 0.44 32 0.80 7,179 25
bb_756_16_34_si1000_r34_Z 0.14.0 25704 x 1112454 13230 x 129276 1.75 3 11.3 46 58
  • On the gross circuit, a RW step of 0.14.0 is 67 times faster, and all 128 threads are used (the dense RW working memory of the full matrix limits 0.12.2 to 32 threads): 270 times more steps in 180 s, and a codeword of the minimum weight 10.
  • For bb_360, the codeword of weight 25 is an upper bound on the circuit distance (Section 2.6); Section 6.1 found one of weight 23.
  • For bb_756, the memory throttle (dense RW working memory capped at about 1.5 GB) allows only 3 RW threads on the reduced matrix ($13230 \times 129276$, about 0.4 GB per thread); on this 236 GB server, nothrottle=1 would run 128 threads (about 55 GB). With 32–64 RW threads, RW runs 6.7–7.4 times more steps per second (Section 6.1); 0.14.3 runs 32 RW threads by default (Section 7.1).

5.5 Where the speedups come from

0.14.0 with merge=0 drop=0 (neither merging nor dropping) and with drop=0 (merging only), against its default (both) and 0.12.2, on the DEM cases of Section 4 (wall time in s; "–": not run, from the budget of 0.12.2, which took 176 s on four threads).

case method $p$ merge=0 drop=0 drop=0 default 0.12.2
bb_72 circuit, stripped DEM 1 1 61.2 59.9 58.2
1 128 0.99 0.89 0.93
2 1 0.094 0.051 1.12
2 128 0.027 0.026 0.042
bb_72 circuit, full DEM 1 1 48.8 45.7 5.56 98.9
1 128 1.21 1.20 0.18 2.14
2 1 28.8 21.7 0.11 –
2 128 0.38 0.32 0.088 9.84
double-gross circuit, stripped DEM 1 1 25.5 20.7 58.9
1 128 1.61 1.40 3.27
2 1 1.13 0.61 12.7
2 128 0.14 0.15 0.27
  • The faster CC of 0.12.3 (the last cluster extension is looked up in a hash table): 3.3–3.9 times on the CSS codes and the LDPC code, 11–12 times on the stripped DEMs, and about 25 times on the full bb_72 DEM (estimated from the four-thread run of 0.12.2); one thread.
  • The faster RW of 0.12.3 on large matrices: 2.0–2.3 times (the LDPC code, the double-gross DEM, the full bb_72 DEM); unchanged on small matrices.
  • Merging the equal columns (0.12.4): 1.0–1.2 times for RW, and 1.3–1.9 times for CC.
  • Dropping detectors (drop=auto, 0.14.0): 8 times for RW and 190 times for CC on the full bb_72 DEM (one thread).

The legacy dist_m4ri_old (one thread, built from the 0.14.0 sources) took, for the RW runs of Section 4, 66.5 s (QX150), 47.7 s (c204H), 203 s (bb_72 stripped), 20.5 s (bb_72 full, reduced), 69 s (gross), 92 s (double gross), 71 s (LDPC), and 85 s (double-gross DEM).

6. Follow-up Runs of 0.14.1 (2026-10-14)

dist_m4ri 0.14.1 (commit 68e5e02), on the server of Section 4, with the full DEMs of Section 5. RW runs use the reduced DEMs (drop=auto, the default) and min_hits=0.

6.1 RW threads for the largest DEMs

RW steps per second against the number of RW threads (method=1, timeout 90 s for bb_360 and 150 s for bb_756, nothrottle=1 threads=N; "default": the throttled run).

DEM searched dense RW memory per thread RW threads RW steps/s s/step/thread
bb_360_12_24_si1000_r24_X 4500 x 43560 49 MB default (32) 45.2 0.70
8 / 16 / 32 14.9 / 31.1 / 45.3 0.54 / 0.51 / 0.70
64 / 128 42.1 / 33.9 1.50 / 3.58
bb_756_16_34_si1000_r34_Z 13230 x 129276 0.43 GB default (3) 0.23 12.2
8 / 16 / 32 0.63 / 1.12 / 1.57 12.0 / 13.4 / 18.8
64 / 128 1.72 / 1.57 31.0 / 49.4
  • The throughput peaks at 32 RW threads for bb_360, the number the throttle allows, and at 32–64 threads for bb_756, where the throttle allows only 3: the memory bus saturates at 32–64 threads whatever the size of the matrix.
  • The run of bb_360 on 16 threads found a codeword of weight 23 (seed 20261014); a second run with the same arguments (150 s) found weight 23 again. The upper bound was 25.

6.2 RW windows on the gross and double-gross DEMs

RW with the column permutations of each step from:

  • hybrid: the default of 0.14.1 (kwin=0), an index window of $\min(512, 3n/4)$ columns on every other step (0.14.3: 256 columns for a DEM, Section 7.2);
  • uniform: uniform permutations only (kwin at least $n$);
  • idx1, idx2: an index window of about one or two rounds of columns on every step (kwin=1456 or kwin=2912 for double gross, 732 or 1464 for gross, with win_mode=1);
  • bfs1: a Tanner-graph ball of about one round on every step (win_mode=0).
case hybrid uniform idx1 idx2 bfs1
gross: steps to weight 10 2.6k, 4.1k, 7.9k 12k, 20k, 26k 0.7k, 2.0k, 6.6k 4.2k, 4.6k, 17k 4.6k, 5.2k, 14k
double gross: lightest in 120 s 20, 18 36, 31 18, 18 18, 18 24, 26
  • gross: three seeds, 128 threads; double gross: two seeds, 32 RW threads (the default).
  • On gross, every configuration finds a codeword of the minimum weight 10 in under 3 s; the window steps need 4–10 times fewer steps than uniform ones.
  • On double gross, uniform steps are hopeless, index windows of one or two rounds found weight 18 in all four runs (the upper bound was 19), the default hybrid in one of two, and Tanner-graph balls are much worse than the index windows (time slabs).
  • A run with kwin=1456 win_mode=1 for 180 s found three distinct codewords of weight 18. They consist of errors of the final data measurements (the last error mechanisms of the DEM), i.e., a logical operator of the code (distance 18) at the time boundary.

6.3 Certified lower bounds from a code-sized model

For a memory circuit, a certified lower bound needs no CC on the DEM:

  1. The checks of the measured basis are read from the detectors after the final data measurement: the final data measurements in such a detector give the support of a check.
  2. One observable per check is added to the circuit: the parity of the final data measurements on its support. It is deterministic, and it is flipped by an error mechanism iff the net effect of the error on the data anticommutes with the check.
  3. The rows $O$ of these observables in the DEM are verified to lie in the row space of the detector matrix $H$: $\mathrm{rank}([H; O]) = \mathrm{rank}(H)$. Then every codeword $x$ of the DEM ($Hx = 0$, $Lx \neq 0$) gives a codeword of the model $(O, L)$ (equal columns merged) of weight at most $|x|$.
  4. The distance of the model, computed by CC with the binary, is therefore a lower bound on the circuit distance.

The model has one column per net effect of a single error on the checks and the observables: about $2.5 n$ columns (the data qubits and the hook errors), with 3–6 nonzeros each. The verification held for all circuits below ($X$ basis).

Circuit model model distance CC on the model circuit distance
bb_72_12_6_si1000_r6_X 36 x 180 5 < 0.1 s 6
bb_90_8_10_si1000_r10_X 45 x 225 7 < 0.1 s 8
bb_108_8_10_si1000_r10_X 54 x 270 6 < 0.1 s 8
gross_144_12_12_si1000_r12_X 72 x 360 8 0.1 s 10
double_gross_288_12_18_si1000_r18_X 144 x 720 12 $w \le 11$: 550 s; $w = 12$: 467 s [12, 18]
bb_360_12_24_si1000_r24_X 180 x 900 $\ge 12$ $w \le 11$: 966 s [12, 23]
  • The CC runs on the double-gross and bb_360 models used 32 threads, and 96 for the round $w = 12$ of double gross.
  • For these schedules, the model is 1–2 below the circuit distance: its lightest codewords do not lift to codewords of the DEM of the same weight. It is still a certified bound, and CC on the model reaches weights which CC on the DEM cannot: CC on the DEM of the double-gross circuit took 2.8 h on 128 threads to certify 11 (Section 5.1).
  • With the gaps of the smaller circuits, the true distances of the double-gross and bb_360 circuits may be well below the upper bounds 18 and 23.

7. RW Windows and Thread Throttle of 0.14.3 (2026-10-14)

dist_m4ri 0.14.3 (commit 741d9a1), on the server of Section 4, with the full DEMs of Section 5; RW runs use the reduced DEMs (drop=auto, the default). The raw data and scripts are in scratch/speedup/ (not in the repository).

7.1 Thread throttle

0.14.3: above 15 MB of dense RW memory per thread, at most 32 threads run RW, with their dense matrices within a quarter of the physical memory (at least 2; 1.5 GB if the physical memory is not known), instead of about 1.5 GB in total (Section 6.1: the memory bus saturates at 32–64 RW threads whatever the size of the matrix). Default runs (method=1 min_hits=0, no threads=):

DEM searched dense RW memory per thread RW threads: 0.14.2 → 0.14.3 RW steps/s: 0.14.2 → 0.14.3
bb_756_16_34_si1000_r34_Z 13230 x 129276 0.43 GB 3 → 32 0.23 → 1.49
bb_360_12_24_si1000_r24_X 4500 x 43560 49 MB 32 → 32 45 → 45

7.2 Window size of the hybrid RW steps

With kwin=0 and $n \ge 500$, every other RW step uses an index window of $W$ consecutive columns, and the others a uniform random permutation. A step finds a codeword if all but one of its columns are pivots. The window columns come first in the elimination order, so that they are pivots unless they depend on earlier window columns, while a column outside is a pivot with probability about $r/n \approx 0.1$ ($r = \mathrm{rank}\,H$). In a DEM, whose errors are in time order, a window is a slab of errors close in time, and its rank is at most the number of detectors they touch. Rank density of windows ($D$ detectors and $L$ columns per round, see below):

DEM (reduced) $D$ $L$ rank / $W$ of $W$ consecutive columns, $W$ = 128 / 256 / 512 / 1024 / 2048
gross 72 676 0.73 / 0.47 / 0.28 / 0.19 / 0.15
mitten_270_54_10_C9xS3_custom_r4_Z 108 1485 0.80 / 0.53 / 0.32 / 0.19 / 0.13
mitten_150_30_8_C5xS3_custom_r5_Z 60 844 0.63 / 0.34 / 0.20 / 0.13 / 0.10
double gross 144 1379 0.90 / 0.72 / 0.49 / 0.28 / 0.19
bb_360_12_24_si1000_r24_X 180 1742 0.91 / 0.80 / 0.56 / 0.34 / 0.22

A window of one round of columns ($L \approx 10 D$) touches about $2D$ detectors, so that most of its columns cannot be pivots. A scan of the window size (a single size, the same hybrid scheme); first, the mean number of steps to a codeword of the minimum weight (six seeds, 16 threads):

DEM (reduced) 128 192 256 384 512 1024 2048
gross ($d = 10$) 3.8k 1.5k 1.8k 1.8k 4.8k 15.5k 22k
mitten_270 custom ($d = 9$) 4.4k 7.5k 3.9k 7.3k 25k 111k 125k
mitten_270 hef ($d = 7$) 30k 3.3k 6.2k 9.5k 15k 13k
mitten_150 custom ($d = 7$) 286 133 352 1200 2.0k

Second, the distinct light codewords found in a fixed number of steps (two or three seeds, 32 RW threads, the default): for double gross, those of weight at most 21 in $2 \cdot 10^4$ steps (in parentheses: of weight 18); for bb_360, those of weight at most 28 in 3000 steps (in parentheses: the lightest weight found):

DEM (reduced) 128 192 256 384 512 $L$ $2L$
double gross 5, 2 (1, 1) 63, 45 (18, 14) 58, 64 (9, 13) 31, 18 (4, 2) 3, 7 (0, 2) 3, 2 (2, 0) 0, 1
bb_360 3, 12 (27, 26) 24, 35, 36 (26, 24, 24) 18, 8 (25, 26) 6, 0 (24, 29) 0 (31) 0 (33)
  • The best window is 192–256 columns for all six DEMs (1.3–3.6 $D$; it does not grow with $D$ from 60 to 180), 2–10 times better than 512: on double gross, about 10 distinct codewords of weight 18 per $2 \cdot 10^4$ steps with 256 columns, and 0–2 with 512 or with one round. 0.14.3 uses 256 columns for a DEM (win_hyb=0; win_hyb=N sets the size).
  • Windows of one and two rounds of columns, alternately, were tried first (from a round estimate): slower than 512. On gross, 9.3k against 4.1k steps to weight 10 (median of five seeds); on mitten_270 custom, 75k–86k against 2k–26k steps; on double gross, a similar time to weight 18; and on bb_360, the lightest weight in 120 s was 29 and 30 against 27 and 25.
  • Cycling through several sizes (e.g., $2L$ down to $L/8$, or $2D$ and $4D$) is worse than the best single size: the optimum is sharp (double gross: 5, 54, and 5 codewords with 128, 192–256, and 512 columns).
  • Where the codewords are: the weight-18 codewords of double gross are errors of the final data measurements, within 177 columns at the end of the DEM; the weight-10 codewords of gross span 120–240 columns, anywhere in time; the weight-9 codewords of mitten_270 custom have 7 columns within about 90, and 2 columns 800–1000 columns later.
  • Matrices of codes gain nothing from 256 columns (c1920H: lightest weights 302–333 with 256 and 297–308 with 512 after $10^3$ steps; the random LDPC code with $n = 3000$: the same; surf_d5, surf_d7, and QX900: saturated), so that 0.14.3 keeps 512 for matrices.
  • Graph distance is no restriction at the scale of the codewords: in the column graph of the reduced double-gross DEM (columns adjacent if they share a detector), the balls of radius 2, 3, 12, and 18 hold about 2.2k, 8.3k (32%), 24.5k (93%), and all 26208 columns (median over 20 seed columns): the spatial layer is covered within 3–4 hops, and then the ball grows by about one round per hop in each time direction. The index windows work because the light codewords are compact in the column order of the DEM.
  • With debug&1, 0.14.3 prints the rounds of a DEM (from the time translation of its errors): $D$ and $L$ as in the table above, $D = 36$ and $L = 319$ for bb_72, $D = 378$ and $L = 3694$ for bb_756, and none for the torus circuits with SWAP routing.

7.3 Codewords found by the uniform and by the window steps

With debug&1, 0.14.3 prints the distinct codewords of the three lowest weights found by each kind of RW step (half of the steps are uniform). Runs with min_hits large and cov_cws=300, so that the 300 lightest codewords are kept:

DEM (reduced) RW steps $w = d$ $w = d + 1$ $w = d + 2$
gross 20000 10: 16, all by windows 11: 113, all by windows 12: 271, 3 by uniform steps
double gross 30000 18: 10, all by windows 19: 10, all by windows 20: 18, all by windows
bb_360 4000 24: 3, all by windows 25: 1, by windows 26: 8, all by windows

The uniform steps find almost none of these codewords: with uniform random information sets, a codeword of weight 10 of gross is found with probability about $1.5 \cdot 10^{-8}$ per step. They are kept for codewords which are not local in the column order (e.g., time-like codewords with one error per round), and for the information-set estimate.

7.4 Time to a codeword of the minimum weight

On the full DEMs of Section 5.2 (method=1, wmin=d, 128 threads, nothrottle=1, three seeds), 0.14.3 finds a codeword of the minimum weight within 0.53 s (median) for all eleven circuits, as 0.14.2. On gross, the steps to weight 10 (five seeds) were 0.5k–5.7k with 256 columns (median 2.0k) against 1.3k–7.3k with 512 (median 3.0k).

8. RW Pairs of 0.14.4 and 0.14.6, and the Model Bound of 0.14.5 (2026-10-15)

dist_m4ri 0.14.5 (commit 6241d59) against 0.14.3 (741d9a1, Section 7) and 0.14.0 (40faf58, Section 5), on the server of Section 4, with the inputs of Section 5: 476 runs in about one hour. 0.14.4 added the RW pairs (pairs, on by default): a RW step also finds the codewords with exactly two non-pivot columns (Lee–Brickell and Stern with $p = 2$), from the pairs of columns which agree on $l$ random pivot rows ($l \approx \log_2(n - r)$, fewer while the upper bound is large). 0.14.5 added compute_model_lower_bound() to the Python wrapper (the code-sized model of Section 6.3, with the minority-basis rows by default until 0.14.6). 0.14.6 bounds the work of the RW pairs per step, after the slow early steps found here (Section 8.7; 142 more runs). The raw data and scripts are in scratch/bench_0.14.5/ (not in the repository).

8.1 Full DEMs: time to a codeword of the minimum weight

As in Section 5.2 (method=1, wmin=d, 128 threads, nothrottle=1), with five seeds per version (seven for gross): the median wall time, which includes reading the DEM, merging, and the exact reduction, and the median number of RW steps; 0.12.2 and 0.9.0 in the figure: the runs of Section 5.2. All runs of 0.14.x found a codeword of weight $d$. 0.14.6: Section 8.7.

Time and RW steps to a minimum-weight codeword in the full DEMs

Circuit $d$ wall (s): 0.14.0 0.14.3 0.14.5 0.14.6 RW steps: 0.14.0 0.14.3 0.14.5 0.14.6
bb_72_12_6_si1000_r6_X 6 0.092 0.092 0.093 0.093 7 6 2 3
mitten_90_18_6_C3xS3_custom_r4_Z 5 0.16 0.16 0.16 0.16 14 8 2 3
mitten_90_18_6_C3xS3_hef_r4_Z 4 0.18 0.18 0.18 0.18 2 1 2 2
mitten_150_30_8_C5xS3_custom_r5_Z 7 0.39 0.37 0.36 0.36 979 413 33 13
mitten_150_30_8_C5xS3_hef_r5_Z 5 0.39 0.38 0.39 0.38 39 121 4 4
mitten_210_42_8_C7xS3_custom_r4_Z 6 0.44 0.44 0.44 0.44 6 6 4 3
mitten_210_42_8_C7xS3_hef_r4_Z 5 0.48 0.47 0.47 0.47 46 32 5 6
mitten_270_54_10_C9xS3_custom_r4_Z 9 1.36 0.64 1.06 0.56 17.3k 1.5k 222 220
mitten_270_54_10_C9xS3_hef_r4_Z 7 1.01 0.68 0.73 0.62 7.8k 1.6k 95 161
mitten_330_66_6_C11xS3_custom_r4_Z 4 0.69 0.70 0.69 0.70 1 1 1 1
mitten_330_66_6_C11xS3_hef_r4_Z 4 0.75 0.74 0.74 0.74 1 1 1 1
gross_144_12_12_si1000_r12_X 10 0.99 0.53 0.44 0.45 7.1k 778 62 62
  • Where many RW steps are needed (mitten_150, mitten_210 hef, mitten_270, gross), 0.14.5 needs 6–30 times fewer than 0.14.3. The wall time is mostly the input stage (0.07–0.7 s), so that the medians hardly change (gross: 0.44 s against 0.53 s). 0.14.5 with pairs=0 behaves as 0.14.3 (gross: 0.51 s, 628 steps).
  • On the mitten_270 circuits, 0.14.5 is slower than 0.14.3 (custom: 1.06 s against 0.64 s; RW alone, from # stopped after, 0.60 s against 0.16 s), although it needs 7–17 times fewer steps. The first codewords found have weights 100–300, and while the upper bound is above about 70, the default $l$ is 1 (with $l = 2$, a codeword of that weight would be kept with a probability below 0.8), so that the steps check millions of pairs: 0.5–5.5 million per step on average over these runs (0.014–0.099 s per step and thread, against 0.003–0.005 s for 0.14.3); the 128 threads spend about 0.1 s in such steps, until the upper bound drops below 20. With a fixed pairs=13 ($\approx \log_2(n - r)$), the upper bound drops to about 10 within a few milliseconds, and so it does with the work bound of 0.14.6 ($l \ge 6$, Section 8.7):
Circuit (median wall time in s / RW time in s / RW steps) 0.14.3 0.14.5 0.14.5, pairs=13 0.14.6
mitten_270 custom ($d = 9$) 0.64 / 0.16 / 1.5k 1.06 / 0.60 / 222 0.56 / 0.12 / 182 0.56 / 0.12 / 220
mitten_270 hef ($d = 7$) 0.68 / 0.16 / 1.6k 0.73 / 0.20 / 95 0.62 / 0.12 / 119 0.62 / 0.12 / 161
mitten_150 custom ($d = 7$) 0.37 / 0.059 / 413 0.36 / 0.056 / 33 0.36 / 0.055 / 20 0.36 / 0.058 / 13
gross ($d = 10$) 0.53 / 0.21 / 778 0.44 / 0.14 / 62 0.45 / 0.14 / 82 0.45 / 0.14 / 62

8.2 Large DEMs: the time to light codewords

RW with the default threads (32 RW threads, Section 7.1) on the full DEMs of the double-gross circuit (wmin=18, three seeds) and of bb_360 (wmin=23, two seeds, timeout 240 s). The time of the first codeword of each weight is that of its message "RW found new upper bound", since the start of the run (reading and reducing the DEM take about 1 s and 2 s). The figure shows 0.14.6 (Section 8.7), which finds these codewords as soon as 0.14.5, against 0.14.3.

The lightest codeword found against time

DEM weight 0.14.3: time (s)/RW steps, per seed 0.14.5 0.14.6 (Section 8.7)
double gross 18 9.6/2.1k, 11.3/2.5k, 18.8/4.9k 1.5/85, 1.8/126, 2.7/329 1.9/224, 1.5/136, 2.4/355
bb_360 24 102, 93 22, 58 8.6, 13
bb_360 23 not in 240 s (10.3k steps each) 118/4.8k, 60/2.2k 119/5.1k, 56/2.2k
  • Double gross: the weight 18 (the lightest known) 6–7 times sooner with the same seed (RW alone: 0.5–1.7 s instead of 8.6–18 s), in 15–25 times fewer steps, each 1.3–1.6 times longer (0.16–0.20 s per step and thread against 0.12–0.13 s).
  • bb_360: the weight 23 (the lightest known, Section 6.1) in 60 and 118 s, while 0.14.3 found 24 (after 93 and 102 s) and nothing lighter in 240 s; a step takes 4–14% longer (0.78–0.85 s per step and thread against 0.74–0.75 s).
  • In 300 s of 0.14.5 (one seed each), nothing lighter was found: double gross with wmin=17 (94k steps; 18 after 2 s) and bb_360 with wmin=22 (12.8k steps; 24 after 4 s, 23 after 41 s).
  • bb_756 (timeout 240 s): 0.14.3 found 55 (371 steps of 20 s per thread). 0.14.5 found 57 after 90 s, but it did not stop at the timeout and was killed after 540 s. With timeout=60, it had completed no RW step after 32 s (the last status line) and was killed after 200 s, while pairs=0 stopped after 62 s (96 steps, weight 61). The first codewords of this DEM have weights of 4000–5000, and while the upper bound is in the hundreds or thousands, the default $l$ is 1–4: a step can then check up to billions of pairs (in 2–16 buckets of the 116k non-pivot columns), and the stop flags are only checked between the buckets. 0.14.6 (Section 8.7) stopped at the timeout, with 55 in 359 steps.

8.3 Codes with a large distance

RW for 30 s (default threads: 128), three seeds: the lightest codeword found by the time $t$ (median of the seeds; the time includes reading the matrix), and at the end (each seed).

code version $t$ = 1 s 2 s 4 s 8 s 16 s 30 s each seed s/step/thread
c1920H ($n = 1920$, $k = 641$) 0.14.3 294 288 277 265 265 257 265, 253, 257 0.0075
0.14.5 257 243 243 243 235 227 234, 225, 227 0.011
0.14.6 257 257 243 243 235 234 234, 234, 227 0.011
random (3,6)-regular LDPC, $n = 3000$ 0.14.3 446 434 432 428 428 422 426, 410, 422 0.013
0.14.5 420 414 402 402 402 402 402, 396, 402 0.044
0.14.6 420 414 402 402 402 402 402, 396, 402 0.046
  • For these distances the default is $l = 1$ (all pairs in two buckets): a step takes 1.5 and 3.5 times longer, and the lightest codeword found is lighter at all times, by about 12% for c1920H (at 30 s: 225–234 against 253–265) and by 3–5% for the LDPC code (396–402 against 410–426). 0.14.6 keeps $l = 1$ for both codes (Section 8.7).
  • In a fixed number of RW steps (1000 on 8 threads), c1920H gives 210, 275, and 277 with the pairs and 320, 321, and 317 without (three seeds; the RW of several threads is not reproducible: an earlier run of the first seed gave 259).

8.4 Default parameters

As in Section 5.3, but with the default parameters of method=1 (steps=100000, min_hits=5) and of method=3 (the exact distance), no threads= (128 threads, throttled), three seeds: median wall time in s / RW steps ("100k": the step limit, min_hits not reached). The runs of 0.14.6 were made 80 min after those of 0.14.5, when the server was up to 10% slower (Section 8.7).

case $d$ method 0.14.0 0.14.3 0.14.5 0.14.6
QX150, one sector 6 1 0.016 / 231 0.016 / 232 0.017 / 70 0.016 / 61
3 0.020 0.019 0.020 0.020
QX900, one sector 8 1 0.051 / 1.5k 0.050 / 1.5k 0.057 / 214 0.054 / 208
3 0.055 0.053 0.058 0.059
c204H 8 1 0.019 / 6.7k 0.019 / 6.4k 0.019 / 3.7k 0.018 / 3.5k
3 0.022 0.021 0.021 0.020
surf_d5 (surf_d5_H.mmx with _L.mmx) 5 1 0.050 / 21.5k 0.051 / 23.1k 0.068 / 1.8k 0.079 / 2.2k
3 0.033 0.031 0.072 0.072
surf_d7 7 1 0.64 / 54.6k 0.66 / 62.7k 1.96 / 100k 2.19 / 100k
3 0.32 0.44 0.49 0.51
bb_72 circuit, stripped DEM 6 1 0.067 / 6.1k 0.068 / 7.0k 0.050 / 1.5k 0.054 / 1.3k
3 0.057 0.056 0.057 0.058
bb_72 circuit, full DEM 6 1 0.12 / 5.9k 0.13 / 6.6k 0.11 / 1.2k 0.11 / 1.3k
3 0.11 0.11 0.11 0.12
mitten_150 custom circuit, full DEM 7 1 2.31 / 100k 2.08 / 100k 1.46 / 43.2k 1.64 / 45.0k
3 0.59 0.61 0.62 0.66
gross, one sector 12 1 0.025 / 8.3k 0.025 / 7.8k 0.026 / 970 0.025 / 941
3 0.033 0.033 0.031 0.031
double gross, one sector 18 1 0.087 / 100k 0.086 / 100k 0.042 / 25.7k 0.046 / 25.1k
3 1.36 1.38 1.37 1.41
gross circuit, full DEM 10 1 8.5 / 100k 8.2 / 100k 10.3 / 100k 11.0 / 100k
  • With the pairs, min_hits=5 is reached in 1.7–13 times fewer RW steps: in about the same time for the small codes, and in less time where 0.14.3 ran to the step limit (double gross: 0.04 s instead of 0.09 s; mitten_150: 1.5 s instead of 2.1 s) or for the bb_72 DEMs (20–26%). method=3 takes the same time (CC dominates), except for surf_d5.
  • surf_d5: 0.068 s against 0.051 s, since a step takes 20 times longer with 128 threads (0.0031 s against 0.00015 s per step and thread; 2.7 times on one thread in the tests of 0.14.4), probably because the codewords of the pairs, about 19 per step, are recorded under the mutex of the codeword table.
  • surf_d7 (surf_d7_H.mmx with _L.mmx: the DEM of a surface-code circuit with $d = 7$ given as matrices, which the binary does not reduce, $336 \times 5473$): 2.0–2.2 s against 0.64–0.66 s, since most runs with the pairs end at the step limit. The hit counts of the 100 codewords of weight 7 tracked for min_hits (cov_cws: the first ones found) are strongly non-uniform in all versions (the binary warns; e.g., one codeword with 184 of 477 hits), so that whether $\langle n \rangle$ reaches 5 within 100k steps depends on the codewords tracked: 0.14.3 also ran to the step limit in one of the three runs, and 0.14.5 converged after 32k steps in one; with the pairs, the tracked set is filled within the first steps. All runs found the distance 7, and method=3 is not affected (CC).
  • The gross circuit (full DEM): all versions run to the step limit; 0.14.5 takes 1.26 times longer (the pairs of each step).

The surface-code circuits of stim (surface_code:rotated_memory_x, $d$ rounds, the uniform noise of $p = 0.001$) as DEMs, which the binary reduces exactly ($d = 7$: $192 \times 883$), with the default method=1 (three seeds; the scripts and logs in scratch/bench_0.14.5/surface/):

circuit 0.14.3 0.14.6
$d = 7$ 0.08–0.09 s (17k–22k steps) 0.08–0.09 s (1.3k steps)
$d = 9$ step limit: 0.55–0.58 s, $\langle n \rangle$ = 1.4–2.1 1.0–1.4 s (23k–35k steps)
$d = 11$ step limit: 2.3 s, $\langle n \rangle$ = 1.1–1.5 step limit: 4.1–4.3 s, $\langle n \rangle$ = 1.2–3.7

With the pairs, min_hits is reached in 13 times fewer steps for $d = 7$ (in the same time), within the step limit for $d = 9$ (0.14.3: not), and with more hits per step for $d = 11$; all runs found the distance $d$.

8.5 Code-sized model lower bound (0.14.5)

compute_model_lower_bound() with the default threads, against the circuit distance (Section 2.6). With minority=False, only the model of the measured-basis chains (Section 6.3) is solved (method=3); with minority=True (the default of 0.14.5 and 0.14.6), the model with all rows is then searched from that bound (RW with wmin equal to the bound, then CC if needed); the times are those of the whole calls. Since 0.14.7, the minority-basis rows are off by default (minority=True, CLI --model-minority, to use them).

Circuit distance model (measured-basis rows) bound time (s) model (all rows) bound time (s)
bb_72_12_6_si1000_r6_X 6 36 x 180 5 0.44 72 x 2664 5 0.28
bb_90_8_10_si1000_r10_X 8 45 x 225 7 0.39 90 x 3330 7 0.45
bb_108_8_10_si1000_r10_X 8 54 x 270 6 0.52 108 x 3996 6 0.52
gross_144_12_12_si1000_r12_X 10 72 x 360 8 0.81 144 x 5328 8 1.33
mitten_90_18_6_C3xS3_custom_r4_Z 5 36 x 306 4 0.27 72 x 4941 4 0.39
mitten_90_18_6_C3xS3_hef_r4_Z 4 36 x 306 4 0.51 72 x 4059 4 0.41
mitten_150_30_8_C5xS3_custom_r5_Z 7 60 x 510 6 0.53 120 x 8230 6 1.04
mitten_150_30_8_C5xS3_hef_r5_Z 5 60 x 510 5 0.63 120 x 6790 5 0.78
mitten_210_42_8_C7xS3_custom_r4_Z 6 84 x 714 5 0.91 168 x 11802 5 1.60
mitten_210_42_8_C7xS3_hef_r4_Z 5 84 x 693 5 0.87 168 x 9597 5 1.20
mitten_270_54_10_C9xS3_custom_r4_Z 9 108 x 918 8 2.03 216 x 15048 8 7.76
mitten_270_54_10_C9xS3_hef_r4_Z 7 108 x 918 7 1.14 216 x 12294 7 10.2
mitten_330_66_6_C11xS3_custom_r4_Z 4 132 x 1089 4 1.08 264 x 18183 4 1.54
mitten_330_66_6_C11xS3_hef_r4_Z 4 132 x 1056 4 1.11 264 x 14432 4 1.54
NNEESEEESEENN_..._n60_k8_d14_X 6 30 x 360 4 0.31 60 x 3810 4 0.41
NEENNWNWNNEEN_..._n120_k8_d15_X 6 60 x 720 6 0.85 120 x 7440 6 0.93
  • The bound (bold: equal to the circuit distance) is tight for the hef Mitten circuits, mitten_330 custom, and the n120 torus circuit (its circuit distance 6 was certified on 2026-10-15, Section 2.6); it is 1 below the distance for bb_72, bb_90, and the other custom Mitten circuits, and 2 below it for bb_108, gross, and the n60 torus circuit.
  • The minority-basis rows raised none of these bounds: the model with all rows has codewords of the same weight. They cost up to 9 s more (mitten_270, where CC on the model with all rows was needed). Nor did they for the surface-code circuits of stim (rotated, $X$ and $Z$ basis, and unrotated, $X$ basis; $d = 5$ and 7, bound $d$ with and without them). With depolarizing-type noise, every net data error which flips the observable of the measured basis also occurs without a component of the other basis, so that a lightest model codeword has a version which the minority-basis rows do not detect; they may raise the bound for other noise models (e.g., biased noise).
  • Against CC on the full DEM (Section 8.6): gross, the bound 8 in 0.8 s against the distance 10 in 184 s; mitten_270 custom, 8 in 2.0 s against 9 in 183 s.

8.6 Certified distances

method=3 with the arguments of Section 5.1 (128 threads), 0.14.5 and 0.14.6 against 0.14.0 (Section 5.1): about the same, since CC dominates (the short runs are about 0.1 s slower, mitten_270 hef is 2 s faster).

Circuit $d$ 0.14.0 (s) 0.14.5 (s) 0.14.6 (s)
mitten_150_30_8_C5xS3_custom_r5_Z 7 0.56 0.63 0.72
bb_90_8_10_si1000_r10_X 8 0.68 0.82 0.88
bb_108_8_10_si1000_r10_X 8 0.71 0.83 0.89
mitten_270_54_10_C9xS3_hef_r4_Z 7 5.8 3.8 3.9
mitten_270_54_10_C9xS3_custom_r4_Z 9 182 183
gross_144_12_12_si1000_r12_X 10 179 184

8.7 A work bound for the RW pairs (0.14.6)

0.14.6 fixes the slow early steps of the RW pairs found above (mitten_270 in Section 8.1, bb_756 in Section 8.2):

  • With pairs=-1 (auto), $l$ is at least the $l$ at which the about $(n-r)^2/2^{l+1}$ pairs of a step are within about the work of its elimination, $rn/16$ pairs (or $2^{20}$ pairs for small matrices). Early in a run, while the upper bound is far above the distance, the keep probability alone gives $l = 1$ (all pairs in two buckets); the bound is $l \ge 6$ for the reduced DEMs of mitten_270 ($r = 648$, $n = 8910$) and bb_756 ($r = 13222$, $n = 129276$), 5 for gross, 4 for mitten_150 and surf_d7, and 1 (no change) for the codes of Section 8.3 and the small matrices of Section 8.4.
  • The stop flags and the upper bound are also polled within the buckets of the pairs (every 65536 pairs), so that a run ends at its timeout also with few rows (e.g., pairs=1).

The runs of Sections 8.1–8.4 and 8.6 with 0.14.6 (the columns 0.14.6 above):

  • mitten_270: 0.56 s (custom) and 0.62 s (hef) to the distance, the fastest of all versions, as with pairs=13; RW alone takes 0.12 s, against 0.60 and 0.20 s with 0.14.5 and 0.16 s with 0.14.3.
  • bb_756 (timeout 240 s): 55 in 359 steps, stopped at the timeout (0.14.3: 55 in 371 steps). With timeout=60, 58 in 53 steps, stopped after 64 s (0.14.5: killed after 200 s; with pairs=0, 61 in 96 steps).
  • The double-gross and bb_360 circuits: the weights 18 and 23 as soon as with 0.14.5, with cheaper steps for double gross (0.12 s per step and thread, against 0.16–0.20 s with 0.14.5, whose early steps with large upper bounds checked many pairs).
  • As with 0.14.5: the other full DEMs, gross, the codes (where $l = 1$ is kept: the same lightest weights), the RW steps of the default runs, and the certified distances. The times of the default runs were 0–16% longer, as were those of 0.14.5 itself at that time: on the gross circuit (full DEM, default parameters, 100k RW steps), five runs of each version, alternating, took 10.7 s (0.14.6) and 11.2 s (0.14.5) in the median, against 10.3 s for 0.14.5 in the runs of Section 8.4.

9. Branch-and-Bound CC Search of 0.15.0 (2026-10-25)

dist_m4ri 0.15.0 (commit 2edf8d7) against 0.14.8 (d43bf47), on the server of Section 4 (idle), with the inputs of Sections 1 and 5.1: 408 runs in 2.8 hours, the two versions alternating case by case. 0.15.0 replaces the CC walk of the earlier versions (all columns of the first unsatisfied row; cc_prune=0) by a branch and bound (cc_prune=1, the default; README, Section 2): each branch forbids the columns of its earlier siblings, the branching row is the unsatisfied row with the fewest available columns, and the packing bound prunes the clusters which cannot be completed within the weight limit. doc/cc_completeness.tex proves that it finds every irreducible codeword up to the weight limit (in particular, every minimum-weight codeword). Distance only (no outC), nothrottle=1 on 128 threads. Both versions give the same distances in all runs. The raw data and scripts are in scratch/bench_0.15.0/ (not in the repository).

9.1 Wall time

method=2 (CC alone, up to the first codeword) and method=3 (the exact distance) on 128 threads, median of three runs (two for the gross and mitten_270 custom circuits), and method=2 on one thread (one run); in parentheses: the speedup of 0.15.0. The codes are given by the matrix finH; the circuits by their full DEMs (Section 5.1).

Input $d$ CC alone, 128 threads method=3, 128 threads CC alone, one thread
yarn_smitten_600_120_14, $H_X$ 14 3.56 → 0.12 s (29x) 3.35 → 0.14 s (24x) 271 → 7.7 s (35x)
yarn_ablp_560_112_14, $H_X$ 14 3.48 → 0.19 s (18x) 3.55 → 0.25 s (14x) 277 → 13.4 s (21x)
yarn_mitten_300_60_14, $H_X$ 14 1.63 → 0.21 s (7.6x) 1.68 → 0.22 s (7.5x) 134 → 15.1 s (8.9x)
double_gross_288_12_18, $H_X$ 18 1.28 → 0.31 s (4.2x) 1.37 → 0.34 s (4.0x) 103 → 24.6 s (4.2x)
yarn_smitten_330_66_12, yarn_mitten_200_40_12 12 2.5x, 1.9x 2.2x, 1.7x
the other codes of Section 1 with $d \le 12$ 4–12 0.82–1.21x (20–30 ms) 0.84–1.11x gross: 0.90x (0.06 s)
gross circuit 10 191 → 77 s (2.5x)
mitten_270 custom circuit 9 193 → 137 s (1.4x)
mitten_270 hef circuit 7 5.34 → 2.54 s (2.1x) 3.79 → 2.06 s (1.8x) 475 → 151 s (3.2x)
bb_90, bb_108 circuits 8 1.11x, 1.12x 1.05x, 1.02x bb_90: 1.14x
the other circuits of Section 5.1 4–7 0.93–0.99x 0.95–1.01x mitten_150 custom: 0.87x
  • The gain grows with the weight of the last CC round: 4–35x for the codes with $d = 14$–18, about 2x for $d = 12$ and for the circuits with $d = 9$–10 (whose CC rounds dominate method=3).
  • The small codes take 20–30 ms, mostly the start-up: their CC work (at most 0.6 thread-s) ranges from 5x lower (yarn_smitten_300) to 1.5x higher (mitten_90, about 1 ms). yarn_mitten_150 takes about 5 ms more (0.82–0.87x), although its CC work is 40% lower.
  • The circuits with $d \le 7$: 0.93–0.99x on 128 threads, except mitten_270 hef (2.1x); on one thread, mitten_150 custom is at 0.87x (the round $w = 6$ has 1.5x fewer nodes, but they cost more).

9.2 Threads, load balance, and predicted work

  • On 128 threads, the CC thread time of the same rounds is 1.41–1.50x that on one thread with 0.15.0 (double gross and the three codes with $d = 14$), and 1.52–1.59x with 0.14.8 (SMT and memory): the branch and bound scales at least as well as the walk. The wall-time speedups $T(1)/T(128)$ are 64–80 for 0.15.0 and 76–83 for 0.14.8 (the runs of 0.15.0 take only 0.12–0.31 s on 128 threads).
  • Load balance: in all CC rounds of 20 s to 42 min (Section 9.3, the gross and mitten_270 custom circuits), the CC thread time is 0.98–1.00 of 128 threads times the wall time of the round.
  • The work of a round predicted from the earlier rounds was within 1–3% of the measured one for the long rounds (e.g., yarn_mitten_975, $w = 23$: $3.16 \cdot 10^5$ thread-s predicted, $3.19 \cdot 10^5$ measured), so that method=3 ends a round which cannot finish before the timeout.
  • 1.7–2.9 million nodes per thread-second (0.34–0.57 µs per node), fewer for the larger codes and weights. With debug&8, 0.15.0 prints the nodes of each CC round, which do not depend on the number of threads.

9.3 Distances of the larger codes of Section 1

method=3 of 0.15.0 on 128 threads (nothrottle=1), one run per sector, with timeouts of 10–60 min. Before: the brackets of Section 1 (short runs of 0.14.7: 20 s per sector for the yarn_* codes, 60 s for the BB codes). In all runs, RW found the upper bound (codewords of the nominal weight, of weight 17 for $d_X$ of yarn_smitten_840), and CC the lower bound. Last CC round: of the slower sector.

Code before 0.15.0: $d_X$, $d_Z$ time last CC round: $w$, thread-s, nodes
yarn_mitten_500_100_16 [15, 16] 16, 16 1.0 s, 1.1 s 15, 87, $2.3 \cdot 10^8$
yarn_smitten_600_120_16 [15, 16] 16, 16 1.2 s, 1.4 s 15, 118, $3.0 \cdot 10^8$
yarn_smitten_840_168_18 [15, 17], [15, 18] 17, 18 3.3 s, 8.9 s 17, 777, $1.7 \cdot 10^9$
yarn_mitten_540_108_18 [15, 18] 18, 18 9.6 s, 9.0 s 17, 857, $2.0 \cdot 10^9$
yarn_smitten_1200_240_20 [14, 20] 20, 20 56 s, 58 s 19, 4990, $1.0 \cdot 10^{10}$
yarn_mitten_630_126_20 [15, 20] 20, 20 91 s, 82 s 19, 8360, $1.8 \cdot 10^{10}$
yarn_mitten_780_156_22 [15, 22] 22, 22 11 min, 9.3 min 21, $6.05 \cdot 10^4$, $1.2 \cdot 10^{11}$
yarn_mitten_975_195_24 [14, 24] [23, 24], 24 20 min, 59 min 23, $3.19 \cdot 10^5$, $5.5 \cdot 10^{11}$
bb_360_12_24 [18, 24] 24 (one sector) 3.2 min 23, $1.6 \cdot 10^4$, $4.4 \cdot 10^{10}$
bb_756_16_34 [17, 34] [26, 34] (one sector) 12 min 25, $5.88 \cdot 10^4$, $1.4 \cdot 10^{11}$
  • All nominal distances are confirmed, except that of yarn_smitten_840_168_18, which is 17 (Section 1).
  • The work of a CC round grows by a factor of 2.8–3.5 per weight for the yarn_* codes (2.4–2.9 for the BB codes); with the walk of 0.14.8, the nodes of the yarn_* codes with $d = 14$ grow by about 5 per weight (e.g., yarn_mitten_300, $w = 12 \to 13$: 3.7x with 0.15.0, 4.9x with 0.14.8). In the round $w = 11$ of yarn_mitten_630, 0.15.0 visits 110x fewer nodes (1.37M against 151M).
  • yarn_mitten_975_195_24: for $d_X$, the round $w = 23$ (about $3.5 \cdot 10^5$ thread-s, 46 min on 128 threads) did not fit in the timeout of the run.
  • bb_756_16_34: the rounds $w = 26$ and 27 would take about 21 and 56 min (2.7x per weight), and the distance 34 is out of reach.

10. Checks of 0.15.1 and the Per-Node Cost of 0.15.2 (2026-10-28)

dist_m4ri 0.15.1 (commit 6d7b2c9, with the CC search of 0.15.0) on the server of Section 4, which was not idle (e.g., method=3 took 94 s instead of the 77 s of Section 9.1 for the gross circuit): 413 runs, mostly on 128 threads with nothrottle=1; then 0.15.2, which lowers the cost of a node of the branch and bound. The raw data and scripts are in scratch/bench_0.15.1_p0/ and scratch/reports/m4_per_node_0.15.2.md (not in the repository).

10.1 The distances of Section 9.3 with the walk (cc_prune=0)

method=2 up to $w = d - 1$ on 128 threads: no codeword up to this weight with any value of cc_prune, so that the walk of the earlier versions, which does not rely on the proof of doc/cc_completeness.tex, confirms the distances of Section 9.3 up to $d = 18$.

Code, sector last round $w$ cc_prune=1 cc_prune=0 nodes of the last round, cc_prune=0 / 1
yarn_mitten_500_100_16, $d_X$ / $d_Z$ 15 1.4 s / 1.3 s 112 s / 107 s 341x / 323x
yarn_smitten_600_120_16, $d_X$ / $d_Z$ 15 1.5 s / 1.7 s 98 s / 92 s 275x / 228x
yarn_smitten_840_168_18, $d_X$ 16 3.6 s 566 s 618x
yarn_smitten_840_168_18, $d_Z$ 17 10.5 s 2319 s 1063x
yarn_mitten_540_108_18, $d_X$ / $d_Z$ 17 10.6 s / 10.3 s 1751 s / 1455 s 686x / 656x
  • The ratio of the nodes grows with the weight, e.g., for $d_Z$ of yarn_smitten_840: 2.1x at $w = 5$, 109x at $w = 12$, 1063x at $w = 17$.
  • cc_prune=0, 1, and 2 find the same codewords (outC) for gross, double gross, and yarn_mitten_300 ($w = d$), and for the DEMs of surf_d3, bb_72 (up to $w = 8$: 1.28M codewords), and mitten_270 hef, also with 1, 16, and 128 threads and with method=3; the nodes of each round do not depend on the number of threads. (cc_prune=0 did not finish the codewords of the gross DEM, $w \le 10$, within 40 min.)

10.2 Start-list exclusion

method=2 up to $w = d - 1$ on 16 threads with a start list (start=) of the columns $0$ and $n/2$ (the first columns of the two blocks of these two-block codes) or $0, \dots, 7$, against separate runs from each listed column; the ratios list / separate (medians of 2–3 runs):

Code 2 columns: nodes, CC work 8 columns: nodes, CC work
gross 0.95, 0.87 0.69, 0.70
double gross 0.96, 0.92 0.78, 0.76
bb_360_12_24 0.95, 0.94 0.71, 0.68

The list finds the union of the codewords of the separate runs, each once (gross, $w = 12$: 293 and 810 codewords with 2 and 8 columns; the separate runs find 314 and 1256).

10.3 method=3 on the full DEMs: 0.14.7 against 0.15.1

Median wall time on 128 threads (24 full DEMs of the circuits of Sections 2 and 5.1); the circuits which take more than 1 s:

Circuit $d$ 0.14.7 0.15.1 0.15.1, cc_prune=0
gross, SI1000 noise 10 212 s 94.3 s (2.25x) 226 s
gross, uniform noise 10 182 s 72.0 s (2.53x) 189 s
yarn_mitten_150 hook-free, $Z$ / $X$ 8 292 s / 116 s 154 s / 62.4 s (1.9x) 285 s / 115 s
mitten_270 custom 9 209 s 150 s (1.39x) 203 s
torus_n200_k16_d16 8 124 s 67.3 s (1.84x) 123 s
torus_n200_k8_d17 8 31.9 s 20.3 s (1.57x) 31.5 s
shyps_225_16_8 8 16.3 s 8.2 s (1.99x) 16.1 s
mitten_270 hef 7 4.07 s 2.29 s (1.78x) 4.00 s
  • With cc_prune=0, 0.15.1 is as fast as 0.14.7 (0.94–1.08x on all 24 circuits), and so is 0.14.5 on the gross and mitten_270 custom circuits: the code of the walk did not change, and the speedup is that of the branch and bound.
  • The other 15 circuits (0.12–0.94 s) run at 0.89–1.06x the speed of 0.14.7 (mostly the start-up).

10.4 Per-node cost (0.15.2)

0.15.2 against 0.15.1 (both built with the makefile) with method=2 on 128 threads, on the idle server; CC work: the CC thread time summed over the rounds. The results are the same, and with cc_prune=1 also the nodes of every round; with cc_prune=2, the cover bounds are used only with at least 4 columns left (with 3, after the packing bound, they rarely prune on DEMs and cost more than they save).

Input rounds cc_prune=1: CC work cc_prune=2: CC work
yarn_smitten_840_168_18, $d_Z$ $w \le 16$ 379 → 364 thread-s (1.04x) 370 → 361 thread-s (1.03x)
yarn_mitten_540_108_18, $d_X$ $w \le 16$ 368 → 350 thread-s (1.05x) 367 → 347 thread-s (1.06x)
double gross, $H_X$ $w \le 17$ 40.3 → 40.2 thread-s (1.00x) 52.1 → 50.0 thread-s (1.04x)
gross DEM $w \le 8$ 792 → 712 thread-s (1.11x) 851 → 737 thread-s (1.16x)
gross DEM $w \le 9$ 10158 → 9060 thread-s (1.12x) 9822 → 9173 thread-s (1.07x)
mitten_270 custom DEM $w \le 7$ 786 → 625 thread-s (1.26x) 945 → 639 thread-s (1.48x)
mitten_270 hef DEM $w \le 6$ 142 → 122 thread-s (1.16x) 194 → 125 thread-s (1.55x)
mitten_150 custom DEM, outC $w \le 8$ 15.2K → 12.2K thread-s (1.25x) 18.5K → 12.5K thread-s (1.48x)
  • On one thread: 1.05–1.06x on codes and 1.04–1.11x on DEMs with cc_prune=1 (yarn_mitten_300, double gross, gross; bb_72, mitten_270 hef, mitten_150 custom), 1.04–1.09x and 1.25–1.39x with cc_prune=2. On 128 threads, the gain on the DEMs is larger.
  • The same codewords (outC) as 0.15.1 for gross, yarn_mitten_300, bb_72, surf_d3 with a start list, and mitten_150 custom ($w \le 8$: 74195 codewords), with both values of cc_prune.
  • cc_prune=2 against cc_prune=1 with 0.15.2 (CC work): 0.89x for yarn_mitten_630_126_20 ($d_X$, $w \le 19$: 11681 against 13077 thread-s), 0.96–0.99x for yarn_mitten_780_156_22 ($d_X$, $w \le 19$), yarn_smitten_840, and yarn_mitten_540 ($w \le 16$, 17), 1.01–1.04x on the DEMs above (0.96–1.00x on two slices of the start columns of the round $w = 10$ of the gross DEM), but 1.23–1.26x for the BB codes: double gross ($w \le 17$), bb_360_12_24 ($w \le 22$: 11619 against 9454 thread-s, 91 s against 74 s), and bb_756_16_34 ($w \le 22$: 6651 against 5281 thread-s). Thus cc_prune=1 stays the default; cc_prune=2 can save up to about 10% in the largest rounds of the yarn_* codes, probably because their columns have the weights 3 and 6 (the cover bounds use the actual numbers of unsatisfied rows of the columns, the syndrome-weight bound only the largest column weight), while all the columns of the BB codes have the weight 3. With 0.15.1, cc_prune=2 was ahead on the gross DEM for $w \ge 9$ (0.97x the CC work of cc_prune=1 for $w \le 9$, 0.77x the time for $w \le 10$ with outC in Section 10.1): there, the cover bounds with 3 columns left still pay off.
Generated by doxygen 1.15.0