Quantum code parameters, checkable by a certificate of provable size
Shuoming An, Fusheng Yang
quant-ph
Oct 2, 2026 · v1
TL;DR
Quantum code parameters, including distance, are certified by certificates whose correctness the Lean kernel checks by computation, with certificate-size bounds proved as Lean theorems.
Abstract
A code is described by three numbers: its physical qubits, its logical qubits, and the smallest error it cannot detect, counted in qubits. The first two are linear algebra. The third, the distance, is an optimum over an exponentially large set, read off a solver whose answer carries no certificate. Whether a code's parameters can be checked uniformly across codes, with a certificate of proved size, is open. Here we show that they can, by moving the unit of work from the code to a certificate, a short object, either a list, a pairing or a symbolic instance, whose correctness the kernel of the \Lean\ proof assistant decides by computation. The kernel is the small core that checks each step. The certificate's size is itself a theorem: its enumeration form lists the vectors of weight below the distance $d$, $\sum_{j<d}\binom{n}{j}$ of them, a polynomial in the code's length $n$ at fixed distance $d$. No bound uniform over codes in both $n$ and $d$ is smaller. For product families the certificate is smaller still, the bound being proved once, symbolically. Deciding that a vector lies outside the row space of the check matrix, the set of sums of its rows, becomes one matrix-vector product and one inner product. On an eighteen-qubit toric code, a surface code closed into a torus, the whole-file check of that decision falls from 42\,s to 9\,s. Eleven code families and thirty-nine parameter sets follow, the widest at 1872 qubits. Nothing beyond the three standard axioms of \Lean's logic is trusted, though the generator that writes a code's checks stops at twenty qubits, and the lower bound for the 144-qubit code is imported rather than proved here. A distance becomes checkable rather than believed, and the same move applies wherever else a computation ends in a solver.
Problem
The distance of a quantum code is an optimum over an exponentially large set and is usually read off solvers that give no certificate. It was open whether code parameters can be checked uniformly across codes using certificates of proved size.
Approach
Code parameters are checked through certificates (lists, pairings, or symbolic instances) that the Lean kernel decides by computation. Vectors are modeled as Fin n → F2, and row reduction runs inside Lean, with theorems that it preserves row space and computes rank and row-space membership. Certificate size is proved to be the sum over j<d of binom(n,j), polynomial in n for fixed d, and this bound is shown to be tight. Hypergraph product families instead use symbolic cleaning-argument lower bounds proved once in Lean.
Results
Eleven code families and thirty-nine parameter sets are kernel-checked, the largest at 1872 qubits, using only Lean's three standard axioms. On an 18-qubit toric code, the row-space non-membership check falls from 42 s to 9 s. The check-generator stops at twenty qubits, and the [[144,12,12]] lower bound is imported rather than proved here.
| Instance | n | d | sum_{j<d} C(n,j) | Route |
|---|
| Hamming [15,11,3] | 15 | 3 | 121 | enumeration |
| BB [[18,4,4]] | 18 | 4 | 988 | enumeration |
| Toric [[18,2,3]] | 18 | 3 | 172 | 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 |
Selected instances: enumeration size vs. 2^n and verification route