four_hadamard_clean_return_phases
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 + 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.
have he : (1 + u) * (1 - w) = -v * ((1 - u) * (1 + w)) := by linear_combination hreturn
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).
uses
congrArg,Complex.normSq,map_mul,Complex.normSq_add,Complex.normSq_sub,map_one,Complex.conj_re,one_mul,Complex.normSq_neghave 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]
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.
uses
Complex.normSq_apply,mul_eq_zero.mphave 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
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).
uses
Complex.exthave hwcase : w = u ∨ w = star u := by rcases him with h | h · left; apply Complex.ext <;> simp_all · right; apply Complex.ext <;> simp_all
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.
uses
mul_eq_zero.mp,Or.inl,Or.inrrcases 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⟩))
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.
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|²
- The deduction of Re(u) = Re(w) on line 13 and (Im(u) - Im(w))(Im(u) + Im(w)) = 0 on line 17 rely on the automated tactic nlinarith to eliminate algebraic cross-terms.
- The polynomial factorizations on lines 28 and 40 are certified algebraically by the linear_combination tactic using the clean-return equation and the unit norm identity u * star u = 1.
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.
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⟩))