Strict reduction of normalized column complexity
OpenQAlgorithms.Papers.Independent.Intakenext100.P03.column_complexity_reductionLet be a positive even integer. Put , , , and , where , and .
Here . Let be the unique prime of above . Its additive ideal-normalized valuation is , with . Define and . A normalized pair has finite complexity even when a coordinate is zero. Suppose , , and . For each integer , construct
Then
The gate order is , and no range restriction on is added. This is the strict descent step for column synthesis.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P03
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P03
open scoped BigOperators Classical
-- Reuse the Mathlib matrix type without declaring a second Mat.
local notation "Mat" => Matrix Bool Bool ℂ
/-- Canonical data: the axis/exponent list and the actual residual matrix D,
not a nonunique phase/Clifford witness pair, PDF pp.6-7. -/
local notation "CanonicalData" => List (Fin 3 × ℕ) × Matrix Bool Bool ℂ
/-- Lemma 7.6, PDF pp.22-23. The output pair is constructed by H0*Uz and k
is an unrestricted integer. Norm preservation is not an assumed output property. -/
theorem column_complexity_reduction (n : ℕ) (hn : SmallParameter n)
(x y : ℂ) (hx : x ∈ cyclotomicSynthesisRing n) (hy : y ∈ cyclotomicSynthesisRing n)
(hnorm : Complex.normSq x + Complex.normSq y = 1)
(hlarge : smallComplexity n < columnComplexity n x y) :
∃ k : ℤ, columnComplexity n (reducedColumn n x y k false)
(reducedColumn n x y k true) < columnComplexity n x y := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every , put , let be the smallest subring of containing , and let be the smallest subring containing and . Define as the intersection of all prime ideals of containing , with an empty intersection equal to the whole ring. For , let be the supremum of natural numbers for which for some ideal , and let be when , and otherwise as an extended real. Define ; for nonzero admitting a natural with , take the least such and set ; for all other nonzero , set . For every satisfying and
there exists an integer , which may be negative or zero, such that, on putting
one has
All valuation arithmetic, minima, negations, and comparisons here are in the extended reals, without an additional hypothesis that these quantities are finite.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.