← All papers
First page of End-to-End Formalization of Quantum Error Correction

End-to-End Formalization of Quantum Error Correction

Mattias Ehatamm, Yi Lee, Xiaodi Wu, Runzhou Tao

quant-ph May 15, 2026 · v1
Presents Lean-QEC, a Lean 4 formalization of stabilizer-code theory delivering machine-checked quantum code distance certificates.
Quantum error-correcting codes (QECCs) sit between noisy quantum hardware and reliable computation, so the code parameters used in practice must be trustworthy. The single number that summarizes a code's strength is its distance, yet certifying a distance lower bound is NP-hard in general, placing it beyond the reach of pen-and-paper proofs as well as direct proof-assistant scripting. As a result, distance values in the literature come either from non-scaling hand proofs, or from unverified solvers that leave a trust gap exactly where the code is supposed to provide a guarantee. We present Lean-QEC, the first Lean 4 formalization of stabilizer-code theory that delivers end-to-end, machine-checked distance certificates at industrial code sizes. Lean-QEC formalizes the linear algebra of qubit states, the Pauli group, stabilizer codes, the binary symplectic representation, classical coding theory, and the CSS and Bivariate Bicycle families. To break the combinatorial barrier, Lean-QEC translates the distance condition into a Boolean satisfiability formula through a verified reduction. The pipeline scales through a BitVec-flattened encoding that replaces Lean's Matrix representation, and an error-location encoding that reduces the variable count from $n$ to $k\lceil \log_2 n\rceil$. With these, we obtain automatically-generated Lean-checked distance proofs for a large range of industrially viable qLDPC codes within the Bivariate Bicycle and Generalized Bicycle families, including [[90, 8, 10]] and [[70, 6, 9]] BB codes, with the formulation scaling up to 144 qubits when performed outside the Lean kernel. The resulting library is reusable and is designed to plug into broader Lean-based efforts toward end-to-end verification of fault-tolerant quantum computation.

Certifying the distance of quantum error-correcting codes is NP-hard, so published distance values rely on either non-scaling hand proofs or unverified computational solvers. This leaves a trust gap for codes intended to guarantee reliable quantum computation.

Lean-QEC formalizes stabilizer-code theory in Lean 4, covering qubit linear algebra, the Pauli group, the binary symplectic representation, classical coding theory, and CSS/Bivariate Bicycle families. To overcome the combinatorial barrier, the distance condition is translated into a SAT formula via a verified reduction. A BitVec-flattened encoding replaces Lean's Matrix type, and an error-location encoding reduces variable count from n to k*ceil(log2 n).

The pipeline produces machine-checked distance proofs for industrially viable qLDPC codes including [[90,8,10]] and [[70,6,9]] Bivariate Bicycle codes. The SAT-based formulation scales up to 144 qubits when run outside the Lean kernel.