AFTD Auto-Formalizing Theoretical Domains

not_can_certify_noiseless_codes_one

theoremverifiedoriginal

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$.

  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.

    lines 3–4

      intro h
      rcases h with ⟨M, s_max, hs_max, hpos, hjm, -⟩
  2. 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$.

    lines 5–6

    uses le_refl

      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
  3. 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.

    lines 7–9

      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 ⟨?_, ?_, ?_⟩
  4. 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}]$.

    lines 10–14

        · intro f
          dsimp
          split_ifs
          · exact (hpos s_max hs_max_in 0).1
          · exact (hpos s_max hs_max_in 0).2
  5. 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$.

    lines 15–16

    uses Equiv.funUnique, Fintype.sum_bool

        · rw [← (Equiv.funUnique (Fin 1) Bool).symm.sum_comp, Fintype.sum_bool]
          simp
  6. 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$.

    lines 17–21

    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
  7. 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$.

    lines 22–23

      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.

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

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