Lemma 6 (Matrix decomposition): arbitrary finite dimension
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.matrixDecompositionLet and let be a unitary complex matrix whose entries lie in . There is a finite word of one- and two-level operations of types , with product , such that
Two-level operations use distinct ordered coordinates. At the empty word gives the unique empty matrix. The result supplies the algebraic factorization used by exact circuit synthesis.
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 6, PDF p.4: arbitrary finite-dimensional matrix factorization, including dimension 0. -/
theorem matrixDecomposition (d : ℕ) (U : Matrix (Fin d) (Fin d) ℂ)
(unitary : U ∈ Matrix.unitaryGroup (Fin d) ℂ) (ring : ∀ i j, InDomega (U i j)) :
∃ w : List (LevelOp d), levelWordMatrix w = U := 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 natural number and every unitary complex matrix , suppose that for every entry there exists a natural number such that . Then for some finite word whose operations are , , or on an ordered pair of distinct coordinates, acting identically on all other coordinates, or the diagonal operation multiplying a single coordinate by . Here multiplies the operation matrices in reverse word order, and the empty word gives . The statement includes , where all entry conditions are vacuous and the empty word represents the unique empty matrix.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.