Lemma 5 (Column lemma): reduce a unit column to e1
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.columnReductionLet and let be a unit vector, so . Then a finite sequence of one- and two-level operations of types has product satisfying
Two-level operations act on distinct ordered coordinates and are the identity elsewhere; a one-level multiplies one coordinate by . The equality retains absolute phase. This reduces an arbitrary-dimensional unit column to the first standard basis vector.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- Lemma 5, PDF p.4: arbitrary positive-dimensional unit columns reduce exactly to e1. -/
theorem columnReduction (d : ℕ) (positive : 0 < d) (u : Fin d → ℂ)
(ring : ∀ i, InDomega (u i)) (normalized : vectorNormSq u = 1) :
∃ w : List (LevelOp d), (levelWordMatrix w).mulVec u =
(fun i => if i = (⟨0, positive⟩ : Fin d) then 1 else 0) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P85
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let and . For every positive natural number and every vector , suppose that for each there exists with , and that . Then there is a finite word of the following operations on : apply
to any ordered pair of distinct coordinates , acting as the identity on every other coordinate, or multiply one coordinate by , leaving every other coordinate unchanged. If is the product of these operation matrices in reverse word order, with , then
The case is included, although no pair of distinct coordinates then exists.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.