Quantum error-correcting code parameters, checkable by a certificate of provable size
The distance of a quantum error-correcting code is a minimum over exponentially many candidates. Reported distances, such as d=12 for the [[144,12,12]] bivariate bicycle code, usually come from external solvers that give no checkable certificate.
Codes are represented as GF(2) row spaces using decidable functions Fin n → F2. Row-reduction routines run inside the Lean kernel, with theorems proving that they preserve row space and compute rank and membership. Short certificates (weight-limited lists, orthogonal pairings, submitted echelon forms, and symbolic instances) are checked by kernel computation, and their size is proved to be at most d·n^(d-1). For hypergraph-product families, formalized cleaning arguments give structured lower bounds that avoid enumeration entirely.
The [[144,12,12]] distance is certified, and the affine-permutation codes published with upper bounds are settled at distances 12 and 14. In total, 11 code families and 39 parameter sets are kernel-checked, up to n=1872, trusting only three standard axioms.
| Instance | n | d | Σ_{j<d} C(n,j) | Route |
|---|---|---|---|---|
| Hamming [15,11,3] | 15 | 3 | 121 | enumeration |
| BB [[18,4,4]] | 18 | 4 | 988 | enumeration |
| HGP toric m=16 | 512 | 16 | 2.8e28 | structured, symbolic in m |
| BB [[144,12,12]] | 144 | 12 | 1.0e16 | transported analytic lower bound |
