not_can_certify_noiseless_codes_one
For any dimension d, a single binary measurement cannot certify noiseless quantum codes, so ¬ can_certify_noiseless_codes d 1 holds.
Statement
theorem not_can_certify_noiseless_codes_one (d : ℕ) : ¬ can_certify_noiseless_codes d 1- Related work
- arXiv:2610.37347
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- can_certify_noiseless_codesA dimension d admits certification of noiseless quantum codes by k binary measurements if there exist a parametrized family of measurement…
- is_jointly_measurable_onA family of k binary measurements M on C^d is jointly measurable on a subspace with orthogonal projection P if there exists a parent POVM…
- certifies_noiseless_codesGiven $M : \mathbb{R} \to \mathrm{Fin}\,k \to \mathrm{Matrix}(\mathrm{Fin}\,d)(\mathrm{Fin}\,d)\mathbb{C}$ and $s_{\max} : \mathbb{R}$,…
Read back from the Lean
For every natural number $d$, it is impossible to certify noiseless quantum codes of dimension $d$ using $k = 1$ measurement operator; that is, can_certify_noiseless_codes d 1 does not hold.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by contradiction: if a single binary measurement could certify noiseless quantum codes, there would exist a parameter $s_{\max} > 1$ such that the measurement $M(s_{\max})$ is jointly measurable on the identity if and only if $s_{\max} \le 1$. However, a single binary POVM $\{M_0, 1 - M_0\}$ is unconditionally jointly measurable with itself at any parameter value, by simply assigning $M_0$ to true and $1 - M_0$ to false. Applying this at $s = s_{\max}$ yields $s_{\max} \le 1$, contradicting $s_{\max} > 1$.
Assume for contradiction that a single binary measurement can certify noiseless quantum codes.
Assuming the negation of the theorem, we unpack the definition of `can_certify_noiseless_codes d 1` into a measurement family $M(s)$ indexed by $\text{Fin } 1$, a parameter threshold $s_{\max} > 1$, the validity condition that each $M(s, 0)$ and $1 - M(s, 0)$ are positive semidefinite for $s \in [0, s_{\max}]$, and the equivalence that $M(s)$ is jointly measurable on the identity if and only if $s \le 1$. The code-recovery condition is discarded.
intro h rcases h with ⟨M, s_max, hs_max, hpos, hjm, -⟩
At $s = s_{\max}$, joint measurability of $M(s_{\max})$ on the identity implies $s_{\max} ≤ 1$.
Because $s_{\max} > 1 > 0$ and $s_{\max} ≤ s_{\max}$ (by `le_refl`), $s_{\max}$ lies in the interval $[0, s_{\max}]$. Specializing the joint measurability equivalence to $s = s_{\max}$ gives that joint measurability on $1$ implies $s_{\max} ≤ 1$.
uses
le_reflhave hs_max_in : s_max ∈ Set.Icc 0 s_max := ⟨by linarith, le_refl _⟩ have hjm_smax := (hjm s_max hs_max_in).mp
Construct a candidate joint measurement witnessing that $M(s_{\max})$ is jointly measurable on the identity $1$.
For $k = 1$, joint measurability requires a POVM $G$ indexed by assignments $f : \text{Fin } 1 → \text{Bool}$. We define $G(f)$ to be $M(s_{\max}, 0)$ if $f(0) = \text{true}$ and $1 - M(s_{\max}, 0)$ if $f(0) = \text{false}$. To establish joint measurability, it remains to verify positivity, normalization (summing to $1$), and marginal consistency.
have hjm_holds : is_jointly_measurable_on (M s_max) 1 := by use fun f => if f 0 then M s_max 0 else 1 - M s_max 0 refine ⟨?_, ?_, ?_⟩
Each operator of the candidate POVM is positive semidefinite.
For any assignment $f$, $G(f)$ evaluates to either $M(s_{\max}, 0)$ or $1 - M(s_{\max}, 0)$. Both matrices are positive semidefinite by the assumed validity of the POVM family $M$ at $s_{\max} \in [0, s_{\max}]$.
· intro f dsimp split_ifs · exact (hpos s_max hs_max_in 0).1 · exact (hpos s_max hs_max_in 0).2
The candidate POVM elements sum to the identity matrix.
Reindexing the sum over $f : \text{Fin } 1 → \text{Bool}$ to a sum over $\text{Bool}$ via `Equiv.funUnique` and expanding the Boolean sum using `Fintype.sum_bool`, the sum becomes $M(s_{\max}, 0) + (1 - M(s_{\max}, 0))$. Simplification reduces this to the identity matrix $1$.
uses
Equiv.funUnique,Fintype.sum_bool· rw [← (Equiv.funUnique (Fin 1) Bool).symm.sum_comp, Fintype.sum_bool] simp
The marginal of $G$ reproduces the single measurement $M(s_{\max})$.
Since the index set $\text{Fin } 1$ is a subsingleton, the measurement index $j$ must equal $0$ by `Subsingleton.elim`. Substituting $j = 0$, the marginal sum retains only the term where $f(0) = \text{true}$. Reindexing over $\text{Bool}$ via `Equiv.funUnique` and `Fintype.sum_bool`, the sum evaluates to $M(s_{\max}, 0) + 0 = M(s_{\max}, 0)$, which simplifies to the required marginal $1 \cdot M(s_{\max}, 0) \cdot 1$.
uses
Subsingleton.elim,Equiv.funUnique,Fintype.sum_bool· intro j have hj : j = 0 := Subsingleton.elim j 0 subst hj rw [← (Equiv.funUnique (Fin 1) Bool).symm.sum_comp, Fintype.sum_bool] simp
A contradiction is reached between $s_{\max} ≤ 1$ and $s_{\max} > 1$.
Having proved that $M(s_{\max})$ is jointly measurable on $1$, the implication derived earlier yields $s_{\max} ≤ 1$. Linear arithmetic detects the contradiction with $s_{\max} > 1$.
have h_le := hjm_smax hjm_holds linarith
le_refl- Every element in a preorder is less than or equal to itself ($a ≤ a$).
Equiv.funUnique- Functions from a singleton domain $\alpha$ to $\beta$ are equivalent to $\beta$, i.e., $(\alpha → \beta) ≃ \beta$.
Fintype.sum_bool- The sum of a function over all Booleans equals $f(\text{true}) + f(\text{false})$.
Subsingleton.elim- Any two elements of a subsingleton type are equal.
- The channel-coding condition in the definition of `certifies_noiseless_codes` is entirely unused; the contradiction arises purely from the requirement that joint measurability of the POVM family characterizes $s ≤ 1$, which fails when $k = 1$ because a single binary POVM is unconditionally jointly measurable.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For any dimension d, no single binary measurement can certify noiseless quantum codes. -/theorem not_can_certify_noiseless_codes_one (d : ℕ) : ¬ can_certify_noiseless_codes d 1 := by intro h rcases h with ⟨M, s_max, hs_max, hpos, hjm, -⟩ have hs_max_in : s_max ∈ Set.Icc 0 s_max := ⟨by linarith, le_refl _⟩ have hjm_smax := (hjm s_max hs_max_in).mp have hjm_holds : is_jointly_measurable_on (M s_max) 1 := by use fun f => if f 0 then M s_max 0 else 1 - M s_max 0 refine ⟨?_, ?_, ?_⟩ · intro f dsimp split_ifs · exact (hpos s_max hs_max_in 0).1 · exact (hpos s_max hs_max_in 0).2 · rw [← (Equiv.funUnique (Fin 1) Bool).symm.sum_comp, Fintype.sum_bool] simp · intro j have hj : j = 0 := Subsingleton.elim j 0 subst hj rw [← (Equiv.funUnique (Fin 1) Bool).symm.sum_comp, Fintype.sum_bool] simp have h_le := hjm_smax hjm_holds linarith