QECert: Formal Foundations for Quantum Error-Correction Theory in Lean
Existing formalizations of quantum error correction cover stabilizer codes and the verification of individual codes. They do not systematically treat the asymptotic constructions and fundamental limitations that scalable quantum error correction depends on.
QECert is a Lean library built on Mathlib. Within one framework it connects the Knill–Laflamme criteria, stabilizer and CSS codes, chain-complex/homology descriptions, and product constructions. The principal case study is asymptotically good qLDPC codes, with formalized constructions and parameter theorems for hypergraph, balanced, and lifted product codes and for quantum Tanner codes. Further formal developments cover Bravyi–Poulin–Terhal locality bounds, constant overhead magic state distillation, and energy barriers and storage errors for quantum memories.
The library formalizes principal results including the Knill–Laflamme theorem, good lifted product and quantum Tanner codes, and the BPT bound with an explicit constant 16384 w^4 log2 q. It also covers triorthogonal codes and distillation thresholds, and the Bravyi–Terhal energy-barrier bound. Its scope is compared against two existing Lean QEC libraries, Lean-QEC and QECLean.
| Library | Research focus | Representative results |
|---|---|---|
| Lean-QEC | Distance certification for stabilizer codes | Stabilizer foundations; verified SAT reduction; distance certificates for CSS and bicycle codes |
| QECLean | Code structures, parameters, logical operators | Stabilizer and homological frameworks; toric, surface, bicycle codes |
| QECert | Asymptotic properties and fundamental limits of QEC | Good qLDPC codes; locality restrictions; distillation costs; energy barriers |
