End-to-End Formalization of Quantum Error Correction
Mattias Ehatamm, Yi Lee, Xiaodi Wu, Runzhou Tao · 2026
Read End-to-End Formalization of Quantum Error Correction by Mattias Ehatamm, Yi Lee, Xiaodi Wu, Runzhou Tao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16523.txt.
Introduction
Ehatamm and three colleagues present Lean-QEC, a first-of-its-kind Lean 4 formalization of stabilizer codes. It delivers machine-checked distance certificates end to end. Certifying a code's distance bound is hard in general, so published distances often rest on unscalable hand proofs. Others rest on unverified solvers that leave a trust gap. A verified satisfiability encoding of the distance condition breaks that barrier. The pipeline produces Lean-checked proofs for industrially viable quantum low-density parity-check codes, reaching 144 qubits outside the Lean kernel.
Catalog record
| CREATOR | Mattias Ehatamm, Yi Lee, Xiaodi Wu, Runzhou Tao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71821 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16523
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
End-to-End Formalization of Quantum Error Correction Mattias Ehatamm, Yi Lee, Xiaodi Wu, Runzhou Tao Abstract 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 n to k ⌈ log 2 n ⌉ 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 ⟧ \llbracket 90,8,10\rrbracket and ⟦ 70 , 6 , 9 ⟧ \llbracket 70,6,9\rrbracket 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. 1 Introduction Quantum computing promises asymptotic speedups on classically intractable problems in cryptography, simulation, optimization, and chemistry [ 25 , 3 , 18 , 11 ] . Realizing those speedups on real hardware, however, is constrained by noise: every physical qubit decoheres and every physical gate is imperfect [ 23 ] , so the only known route to scalable computation passes through a thick layer of quantum error correction (QEC). Recent experimental demonstrations of QEC on superconducting and trapped-ion platforms [ 26 , 22 , 24 ] have made this layer a load-bearing component of the quantum stack rather than a theoretical curiosity, and have accordingly raised the bar for the trust placed on it. The classical engineering response to such load-bearing code is testing, but testing is essentially unavailable for quantum programs. Output distributions are exponentially expensive to sample, intermediate measurements collapse the very state under inspection, and the noise that motivates correction also corrupts any would-be observation. The remaining option is to formally verify the QEC layer [ 8 , 27 ] : state its guarantees as theorems and discharge them in a proof assistant whose kernel can be independently trusted. Why the distance number is hard to trust. The most informative single parameter of a stabilizer code is its distance d : the minimum Pauli weight of an undetectable error. A code with distance d corrects \lfloor(d-1)/2\rfloor errors, so distance is the value most often quoted when codes are compared and the value on which fault-tolerance thresholds depend. Yet certifying a distance lower bound is computationally hard: even for classical linear codes the problem is NP-complete [ 29 ] , and for stabilizer codes lacking strong symmetry the situation inherits the same intractability [ 15 ] . The values quoted in the literature therefore come from one of two unsatisfying places: • Hand proofs inside a proof assistant. Existing developments such as the 9-qubit Shor-code verification [ 9 ] enumerate every Pauli error explicitly. The bookkeeping — 3n single-qubit error patterns plus all of their combinations — has so far prevented this style from scaling past nine qubits, well short of any code used in current experiments. • Unverified symbolic computation. ILP solvers, custom search routines, or computer-algebra scripts can in principle handle larger codes [ 30 ] , but their outputs sit entirely outside the proof kernel. A distance value pasted from such a tool is the moral equivalent of a numerical constant trusted on faith. Neither option is end-to-end: the first does not scale, and the second leaves a trust gap at exactly the point the code is meant to provide a guarantee. Why end-to-end matters. A pragmatic shortcut is to declare a stabilizer code by its binary symplectic representation and treat distance as a property of that matrix. This makes the math tractable, but it shifts the trust to an informal equivalence between two definitions — the matrix view and the original quantum-theoretic view in which a stabilizer code is the simultaneous +1 eigenspace of a set of Pauli matrices. A genuinely trustworthy artifact must close that loop inside the proof kernel: distance bounds proved over the matrix view must transport, by a machine-checked theorem, to the eigenspace view. Our approach. We present Lean-QEC , a Lean 4 library that builds the stabilizer-code stack end-to-end and discharges distance certificates against industrial-scale codes by combining the proof assistant with an external SAT solver. The library covers the linear algebra of qubit states, the Pauli group with phases, stabilizer codes, the binary symplectic representation, classical coding theory, CSS codes, and the Bivariate Bicycle (BB) family. Each abstraction layer is connected to the next by a machine-checked correspondence theorem, so a distance bound established on a binary symplectic matrix is also a theorem about the corresponding quantum code. For the computationally hard step, Lean-QEC reduces “distance \geq d ” to the unsatisfiability of a Boolean formula via a Lean-verified translation, hands the formula to CaDiCaL through Lean’s bv_decide tactic, and reconstructs the resulting LRAT certificate as a Lean proof term. The trusted base remains Lean’s kernel plus the LRAT checker; the SAT solver itself is not trusted. Making this pipeline scale required two non-obvious design moves, both of which we present as contributions in their own right: 1. Instantiating the Boolean formula directly through Mathlib’s Matrix type exhausts memory well before reaching the [[90,8,10]] BB code. We introduce a BitVec -flattened intermediate representation, prove it consistent with the Matrix -based reference, and use it to carry the encoding past the 90-qubit mark. 2. Even with an efficient encoding, a one-Boolean-per-qubit error variable produces a formula whose solver runs become intractable beyond about 90 qubits. We instead let the variables encode the locations of the (at most d-1 ) nonzero error entries, shrinking the variable count from n to k\lceil\log_{2}n\rceil . For the [[144,12,12]] BB code this is 88 variables versus 144 — a difference that makes 144 qubits tractable outside the kernel in minutes. Contributions. Our contributions are as follows. 1. An end-to-end Lean 4 formalization of stabilizer-code theory. We give a machine-checked development that connects qubit states, the Pauli group with phases, stabilizer codes, the binary symplectic representation, and classical coding theory, with explicit correspondence theorems between adjacent layers ( Section 3 ). 2. A verified reduction from code distance to Boolean satisfiability. We formalize a translation from the stabilizer-theoretic distance condition to an UNSAT query, prove the reduction sound in Lean, and