← All papers
First page of Quantum error-correcting code parameters, checkable by a certificate of provable size

Quantum error-correcting code parameters, checkable by a certificate of provable size

Shuoming An, Fusheng Yang

quant-ph Oct 2, 2026 · v2
Certifies quantum error-correcting code parameters [[n,k,d]] using certificates checked by computation in the Lean kernel, relying only on three standard axioms.
Quantum error correction protects quantum information by encoding it in a code described by three numbers: how many physical qubits it uses, how many logical qubits it protects, and the smallest error it cannot detect. The last is an optimum over exponentially many candidates, so it is read off a solver rather than checked. Here we show that code parameters can be certified by a short certificate, a list or a pairing or a symbolic instance, whose correctness the kernel of a proof assistant decides by computation, and whose size is itself a theorem rather than an estimate. Two published code families have distances settled here: the bivariate bicycle code's $[[144,12,12]]$, certified, and the affine-permutation codes printed at $[[1152,580,\le 12]]$ and $[[2304,1156,\le 14]]$, settled at twelve and fourteen. Eleven code families and thirty-nine parameter sets follow, with nothing beyond three standard axioms trusted and the pipeline's specification step preset to twenty columns.

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.

InstancendΣ_{j<d} C(n,j)Route
Hamming [15,11,3]153121enumeration
BB [[18,4,4]]184988enumeration
HGP toric m=16512162.8e28structured, symbolic in m
BB [[144,12,12]]144121.0e16transported analytic lower bound
Selected certified instances: weight-limited list size vs. full space