§7, unnumbered: matrix decomposition operation count
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.matrixOperation_boundThere is an absolute constant such that, for every unitary matrix over whose least natural denominator exponent is , the successive-column elimination trace returns a reduction word and its expanded inverse satisfying
The inverse word uses only the same one-/two-level alphabet, expanding inverses of and into seven positive copies. Constants precede all matrix data. This bounds the factorization output of Lemma 6; it does not bound arithmetic time.
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 : ℝ) : ℂ)
/-- Section 7, PDF pp.6–7: output of column elimination is O(3^d k), uniformly in U,d,k. -/
theorem matrixOperation_bound :
∃ C : ℕ, 0 < C ∧ ∀ (d : ℕ) (U : Matrix (Fin d) (Fin d) ℂ) (k : ℕ),
U ∈ Matrix.unitaryGroup (Fin d) ℂ → (∀ i j, InDomega (U i j)) →
LeastMatrixExponent U k → 0 < k →
∃ w : List (LevelOp d), MatrixTrace U k w ∧ levelWordMatrix w * U = 1 ∧
levelWordMatrix (inverseWord w) = U ∧
w.length ≤ C * 3 ^ d * k ∧ (inverseWord w).length ≤ C * 3 ^ d * k := 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 , let , and let . Let denote the supplied complex constant sqrtTwo, whose defining equation is not supplied. A vector or matrix has exponent when multiplying every component or entry by places it in ; a matrix has least exponent when it has exponent and for every natural number that is also an exponent for it. For , let be its chosen coefficient quadruple modulo , using zero when . For quadruples in , put , define , with , and put ; a quadruple is reducible when for some . Level operations on coordinates apply , , or to an ordered pair of distinct coordinates, acting identically on the others, or multiply one coordinate by . Write for the reverse-ordered product of a word’s operation matrices, with . For a two-component vector , define by searching, in order, the empty -word, the eight words consisting of letters followed by for , and the sixty-four ordered concatenations of two of these eight words; choose the first whose matrix sends to exponent , or the empty word if none succeeds, with natural subtraction truncated at zero. A pass trace from at exponent may stop with the empty word when all are reducible, or choose distinct with not reducible and , apply on those coordinates, and concatenate a further pass trace at exponent from the resulting vector. A column trace targeting coordinate at exponent zero starts from a vector supported at a coordinate with value , for some , and uses the word swapping by if necessary and then applying single-coordinate -phases at ; a column trace at exponent concatenates a pass trace at exponent with a column trace at exponent from the resulting vector. A matrix trace for a matrix at any exponent is the empty word; for a matrix at exponent , it consists of a column-trace word targeting coordinate zero from the first column of at exponent , followed by a matrix-trace word for the matrix obtained from by deleting row and column zero, at exponent , with every coordinate index in this latter word increased by one. Finally, define by reversing , keeping each and operation unchanged, and replacing each operation and each single-coordinate -phase by seven repetitions of that operation. There exists a positive natural number such that, for every natural number , every unitary complex matrix whose entries lie in , and every positive natural number that is its least exponent, there exists a level-operation word admitting the matrix trace just described for at exponent , with
The constant is independent of . Although is quantified, its hypotheses cannot hold with , since the empty matrix has every exponent and hence least exponent zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.