Instructions of one time stamp of the elimination program write to distinct ids
ProvedOPI.GEP.stage_noduplean-formalizationquantum-algorithmstwo-fold-opi-construction
Oblivious Gauss–Jordan elimination on an augmented system is written as a straight-line program. This is a list of instructions over a field , each consisting of a destination id, a list of source ids and an operation. Ids are natural numbers laid out as
where is a time stamp, a kind, and indices. The instructions with time stamp form the list :
- : the initial matrix entries (computed from the inputs by the given source and operation data ) and the used flags;
- for each column , a block of time stamps starting at : initialization of the pivot accumulator and "found" flag, selection and found flags row by row, accumulation of the pivot row, normalization, and elimination together with the new used flags;
- then the partial sums of the particular solution, followed by the output combinations .
Statement. For all parameters , coefficients , input data , and every time stamp , the destination ids of the instructions of are pairwise distinct:
Together with the fact that each instruction of has destination time stamp , this shows that all destinations of the whole program are distinct, one of the well-formedness conditions in prog_timeOK.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part01
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI OPI.GEP
variable {K : Type} [Field K] [DecidableEq K]
variable (R C Kd : ℕ) (coef : ℕ → ℕ → K) (a0src : ℕ → ℕ → List ℕ) (a0op : ℕ → ℕ → List K → K)
Formal statement
theorem OPI.GEP.stage_nodup (t : ℕ) : ((stage R C Kd coef a0src a0op t).map KIns.dst).Nodup := by sorry
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/GEProg.lean#L577-L658