AFTD Auto-Formalizing Theoretical Domains

four_hadamard_clean_return_phases

theoremverified

For unit complex u,v,w, the clean-return equation (1+u)*(1-w)+v*(1-u)*(1+w)=0 implies one of: u=w=1; u=w=-1; v=1 and u*w=1; or v=-1 and u=w.

Statement

theorem four_hadamard_clean_return_phases (u v w : ℂ)
    (hu : Complex.normSq u = 1) (hv : Complex.normSq v = 1)
    (hw : Complex.normSq w = 1)
    (hreturn : (1 + u) * (1 - w) + v * (1 - u) * (1 + w) = 0) :
    (u = 1 ∧ w = 1) ∨ (u = -1 ∧ w = -1) ∨
      (v = 1 ∧ u * w = 1) ∨ (v = -1 ∧ u = w)
Source
Supporting algebra for OP-3, arXiv:2610.01024, Section E.1; developed in deep session IN-184. These helpers do not establish a lower bound for arbitrary circuit gate lists.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

Equating the squared complex norms of both sides of the rearranged clean-return equation (1+u)(1-w) = -v(1-u)(1+w) shows that Re(u) = Re(w). Together with the unit norm constraints |u| = |w| = 1, this implies that Im(u) = ±Im(w), so either w = u or w = star u. Substituting each case back into the return equation factors it into a product of linear terms, yielding the four claimed solution branches.

  1. (1 + u) * (1 - w) = -v * ((1 - u) * (1 + w))

    The clean-return equation (1 + u) * (1 - w) + v * (1 - u) * (1 + w) = 0 is rearranged by moving the second term to the right-hand side.

    lines 7–8

      have he : (1 + u) * (1 - w) = -v * ((1 - u) * (1 + w)) := by
        linear_combination hreturn
  2. u.re = w.re

    Taking the squared complex norm on both sides of the rearranged return equation, using multiplicativity of the norm, |-v|² = |v|² = 1, and expanding |1 ± z|² = 1 + |z|² ± 2 Re(z) with |u|² = |w|² = 1, simplifies the equation to (2 + 2 Re(u))(2 - 2 Re(w)) = (2 - 2 Re(u))(2 + 2 Re(w)). Expanding both sides yields 8(Re(u) - Re(w)) = 0, giving Re(u) = Re(w).

    lines 9–13

    uses congrArg, Complex.normSq, map_mul, Complex.normSq_add, Complex.normSq_sub, map_one, Complex.conj_re, one_mul, Complex.normSq_neg

      have hn := congrArg Complex.normSq he
      simp only [map_mul, Complex.normSq_add, Complex.normSq_sub,
        hu, hw, map_one, Complex.conj_re, one_mul] at hn
      rw [Complex.normSq_neg, hv] at hn
      have hre : u.re = w.re := by nlinarith [hn]
  3. u.im = w.im ∨ u.im = -w.im

    Expanding the unit norm conditions |u|² = 1 and |w|² = 1 as (Re u)² + (Im u)² = 1 and (Re w)² + (Im w)² = 1, and substituting Re(u) = Re(w), subtracting the two equations yields (Im u)² - (Im w)² = (Im u - Im w)(Im u + Im w) = 0. Therefore, the imaginary parts are either equal or opposite.

    lines 14–20

    uses Complex.normSq_apply, mul_eq_zero.mp

      have him : u.im = w.im ∨ u.im = -w.im := by
        simp only [Complex.normSq_apply] at hu hw
        rw [hre] at hu
        have : (u.im - w.im) * (u.im + w.im) = 0 := by nlinarith [hu, hw]
        rcases mul_eq_zero.mp this with h | h
        · left; linarith
        · right; linarith
  4. w = u ∨ w = star u

    A complex number is uniquely determined by its real and imaginary parts. Since Re(w) = Re(u), the case Im(u) = Im(w) gives w = u, while Im(u) = -Im(w) gives w = star u (the complex conjugate of u).

    lines 21–24

    uses Complex.ext

      have hwcase : w = u ∨ w = star u := by
        rcases him with h | h
        · left; apply Complex.ext <;> simp_all
        · right; apply Complex.ext <;> simp_all
  5. The conclusion holds in the case where w = u

    Substituting w = u into the clean-return equation yields the factorization (1 - u)(1 + u)(1 + v) = 0. Setting each factor to zero gives: 1 - u = 0 implies u = 1 (and thus u = w = 1); 1 + u = 0 implies u = -1 (and thus u = w = -1); or 1 + v = 0 implies v = -1 (and thus v = -1 with u = w). In each branch, one of the disjuncts of the theorem holds.

    lines 25–36

    uses mul_eq_zero.mp, Or.inl, Or.inr

      rcases hwcase with hwu | hwu
      · subst w
        have hf : (1 - u) * (1 + u) * (1 + v) = 0 := by
          linear_combination hreturn
        rcases mul_eq_zero.mp hf with h | h
        · rcases mul_eq_zero.mp h with h | h
          · have : u = 1 := by linear_combination -h
            exact Or.inl ⟨this, this⟩
          · have : u = -1 := by linear_combination h
            exact Or.inr (Or.inl ⟨this, this⟩)
        · have : v = -1 := by linear_combination h
          exact Or.inr (Or.inr (Or.inr ⟨this, rfl⟩))
  6. The conclusion holds in the case where w = star u

    When w = star u, we have u * star u = |u|² = 1. Combining this with the clean-return equation gives the factorization (1 - u)(1 + u)(1 - v) = 0. Setting each factor to zero gives: 1 - u = 0 implies u = 1 and w = star 1 = 1; 1 + u = 0 implies u = -1 and w = star(-1) = -1; or 1 - v = 0 implies v = 1, which together with u * w = u * star u = 1 yields v = 1 ∧ u * w = 1. This exhausts all cases.

    lines 37–48

    uses Complex.mul_conj, mul_eq_zero.mp, Or.inl, Or.inr

      · subst w
        have hc : u * star u = 1 := by simpa [Complex.mul_conj] using hu
        have hf : (1 - u) * (1 + u) * (1 - v) = 0 := by
          linear_combination -u * hreturn - (1 + u - v + u*v) * hc
        rcases mul_eq_zero.mp hf with h | h
        · rcases mul_eq_zero.mp h with h | h
          · have hh : u = 1 := by linear_combination -h
            exact Or.inl ⟨hh, by simp [hh]⟩
          · have hh : u = -1 := by linear_combination h
            exact Or.inr (Or.inl ⟨hh, by simp [hh]⟩)
        · have hh : v = 1 := by linear_combination -h
          exact Or.inr (Or.inr (Or.inl ⟨hh, hc⟩))
congrArg
Functions produce equal outputs on equal inputs: if a = b, then f(a) = f(b)
Complex.normSq
The squared norm of a complex number, |z|², viewed as a multiplicative homomorphism from ℂ to ℝ
map_mul
A multiplicative homomorphism preserves products: f(xy) = f(x)f(y)
Complex.normSq_add
The squared norm of a sum: |z + w|² = |z|² + |w|² + 2 Re(z * conj(w))
Complex.normSq_sub
The squared norm of a difference: |z - w|² = |z|² + |w|² - 2 Re(z * conj(w))
map_one
A unital homomorphism maps 1 to 1: f(1) = 1
Complex.conj_re
The real part of a complex conjugate equals the real part of the original number: Re(conj(z)) = Re(z)
one_mul
One is a left identity for multiplication: 1 * a = a
Complex.normSq_neg
The squared norm of a negation equals the squared norm: |-z|² = |z|²
Complex.normSq_apply
The formula for the squared norm in terms of real and imaginary parts: |z|² = (Re z)² + (Im z)²
mul_eq_zero.mp
In a domain, if a product is zero, then at least one factor is zero: a * b = 0 implies a = 0 or b = 0
Complex.ext
Two complex numbers are equal if their real and imaginary parts are respectively equal
Or.inl
Introduces a disjunction from its left disjunct: A implies A ∨ B
Or.inr
Introduces a disjunction from its right disjunct: B implies A ∨ B
Complex.mul_conj
The product of a complex number with its complex conjugate equals its squared norm: z * conj(z) = |z|²

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

theorem four_hadamard_clean_return_phases (u v w : ℂ)    (hu : Complex.normSq u = 1) (hv : Complex.normSq v = 1)    (hw : Complex.normSq w = 1)    (hreturn : (1 + u) * (1 - w) + v * (1 - u) * (1 + w) = 0) :    (u = 1 ∧ w = 1) ∨ (u = -1 ∧ w = -1) ∨      (v = 1 ∧ u * w = 1) ∨ (v = -1 ∧ u = w) := by  have he : (1 + u) * (1 - w) = -v * ((1 - u) * (1 + w)) := by    linear_combination hreturn  have hn := congrArg Complex.normSq he  simp only [map_mul, Complex.normSq_add, Complex.normSq_sub,    hu, hw, map_one, Complex.conj_re, one_mul] at hn  rw [Complex.normSq_neg, hv] at hn  have hre : u.re = w.re := by nlinarith [hn]  have him : u.im = w.im ∨ u.im = -w.im := by    simp only [Complex.normSq_apply] at hu hw    rw [hre] at hu    have : (u.im - w.im) * (u.im + w.im) = 0 := by nlinarith [hu, hw]    rcases mul_eq_zero.mp this with h | h    · left; linarith    · right; linarith  have hwcase : w = u ∨ w = star u := by    rcases him with h | h    · left; apply Complex.ext <;> simp_all    · right; apply Complex.ext <;> simp_all  rcases hwcase with hwu | hwu  · subst w    have hf : (1 - u) * (1 + u) * (1 + v) = 0 := by      linear_combination hreturn    rcases mul_eq_zero.mp hf with h | h    · rcases mul_eq_zero.mp h with h | h      · have : u = 1 := by linear_combination -h        exact Or.inl ⟨this, this⟩      · have : u = -1 := by linear_combination h        exact Or.inr (Or.inl ⟨this, this⟩)    · have : v = -1 := by linear_combination h      exact Or.inr (Or.inr (Or.inr ⟨this, rfl⟩))  · subst w    have hc : u * star u = 1 := by simpa [Complex.mul_conj] using hu    have hf : (1 - u) * (1 + u) * (1 - v) = 0 := by      linear_combination -u * hreturn - (1 + u - v + u*v) * hc    rcases mul_eq_zero.mp hf with h | h    · rcases mul_eq_zero.mp h with h | h      · have hh : u = 1 := by linear_combination -h        exact Or.inl ⟨hh, by simp [hh]⟩      · have hh : u = -1 := by linear_combination h        exact Or.inr (Or.inl ⟨hh, by simp [hh]⟩)    · have hh : v = 1 := by linear_combination -h      exact Or.inr (Or.inr (Or.inl ⟨hh, hc⟩))
See it in the graphDiscuss this resultChallenge it