AFTD Auto-Formalizing Theoretical Domains

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.
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
See it in the graphDiscuss this resultChallenge it