quantum_hamming_bound
theoremverifiedformalizationimported Lean
Quantum Hamming bound for non-degenerate codes. Let $C \le \mathcal{H}_n$ be a subspace of the $n$-qubit Hilbert space whose complex dimension is $\dim_{\mathbb{C}} C = 2^k$, and suppose $k \le n$. If $C$ is a non-degenerate code correcting $t$ errors — meaning it satisfies the Knill–Laflamme condition $P_C\,E^\dagger F\,P_C = \lambda_{EF}\,P_C$ for all Pauli strings $E,F$ of weight at most $t$, and moreover $P_C\,E^\dagger F\,P_C = 0$ whenever $E \ne F$, where $P_C$ is the orthogonal projection onto $C$ — then \[ \sum_{j=0}^{t} \binom{n}{j}\, 3^{\,j} \;\le\; 2^{\,n-k}. \]
Statement
set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open scoped Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in open Complex Matrix in theorem quantum_hamming_bound (n k t : ℕ) (C : Submodule ℂ (Hn n)) (h_dim : Module.finrank ℂ C = 2^k) (h_nondeg : IsNondegenerate n C t) (hkn : k ≤ n) : ∑ j ∈ Finset.range (t + 1), n.choose j * 3 ^ j ≤ 2 ^ (n - k)
- Formalizes
- Quantum Hamming bound for non-degenerate codes, as formalized in TCSlib (`quantum_hamming_bound`)
- Lean proof
- By Allan Li, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.quantum_hamming_bound← quantum_hamming_bound (TCSlib/ErrorCorrectingCodes/QuantumHamming.lean:485): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- quantum_hamming_bound_rawQuantum Hamming bound for non-degenerate codes. Let $C \le \mathcal{H}_n$ be a subspace of the $n$-qubit Hilbert space that is a…
- HnThe $n$-qubit Hilbert space $\mathcal{H}_n = \ell^2\!\bigl(\{0,1\}^n,\mathbb{C}\bigr)$, implemented as \texttt{EuclideanSpace ℂ (Fin n →…
- IsNondegenerateA code is non-degenerate if it satisfies the Knill--Laflamme condition and additionally $P_C E^\dagger F P_C = 0$ whenever…
- codeProj_applyAction of the code projection. Let $C$ be a closed subspace of the $n$-qubit Hilbert space $\mathcal{H}_n$, and let…
- instFintypePauliStringinstFintypePauliString
- instFiniteDimensionalComplexSubtypeHnMemSubmoduleinstFiniteDimensionalComplexSubtypeHnMemSubmodule
Lean source view module on GitHub
set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open scoped Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in open Complex Matrix in /-- Quantum Hamming bound: a non-degenerate `[[n, k]]` quantum code correcting t errors satisfies `∑ j ∈ Finset.range (t + 1), C(n, j) * 3^j ≤ 2^(n - k)`. -/ theorem quantum_hamming_bound (n k t : ℕ) (C : Submodule ℂ (Hn n)) (h_dim : Module.finrank ℂ C = 2^k) (h_nondeg : IsNondegenerate n C t) (hkn : k ≤ n) : ∑ j ∈ Finset.range (t + 1), n.choose j * 3 ^ j ≤ 2 ^ (n - k) := by classical have hraw := quantum_hamming_bound_raw (n := n) (k := k) (t := t) (C := C) h_dim h_nondeg -- rewrite RHS: 2^n = 2^((n-k)+k) = 2^(n-k) * 2^k have hmul : (∑ j ∈ Finset.range (t + 1), n.choose j * 3 ^ j) * 2^k ≤ (2^(n - k)) * 2^k := by rwa [ ← pow_add, Nat.sub_add_cancel hkn ] have hkpos : 0 < 2^k := Nat.two_pow_pos k exact Nat.le_of_mul_le_mul_right hmul hkpos