← All papers
First page of QECert: Formal Foundations for Quantum Error-Correction Theory in Lean

QECert: Formal Foundations for Quantum Error-Correction Theory in Lean

Keming He, Jiahan Chen, Enji Xiong, Zhongyi Ni, Lei Zhang, Xin Wang

quant-ph Nov 3, 2026 · v1
Develops QECert, a Lean/Mathlib library formalizing quantum error-correction theory, including qLDPC code constructions, locality bounds, magic state distillation, and quantum memories.
Quantum error correction provides the mathematical basis for protecting quantum information against noise. Existing formalizations have established foundations for stabilizer codes and code verification. However, a systematic formal treatment of the asymptotic constructions and fundamental limitations that underpin scalable quantum error correction is still needed. We present QECert, a Lean library providing reusable formal foundations for these theoretical questions. It connects quantum error-correction criteria, stabilizer and Calderbank-Shor-Steane codes, and algebraic and homological constructions within a common framework. Asymptotically good quantum low density parity check codes provide the principal case study. We formalize constructions and asymptotic parameter theorems spanning hypergraph products, balanced products, lifted products, and quantum Tanner codes. Further developments cover Bravyi-Poulin-Terhal bounds and related locality restrictions, constant overhead magic state distillation, and energy barriers and storage errors for quantum memories. QECert establishes a reusable formal foundation for studying the capabilities, resource requirements, and fundamental limitations of quantum error correction, supporting systematic verification and further development of its theory.

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.

LibraryResearch focusRepresentative results
Lean-QECDistance certification for stabilizer codesStabilizer foundations; verified SAT reduction; distance certificates for CSS and bicycle codes
QECLeanCode structures, parameters, logical operatorsStabilizer and homological frameworks; toric, surface, bicycle codes
QECertAsymptotic properties and fundamental limits of QECGood qLDPC codes; locality restrictions; distillation costs; energy barriers
Comparison of Lean libraries for QEC