The generator computes correctly from the parsed input
ProvedOPI.Gen.kdN_eqSetting. An instance of the two-fold OPI problem of Theorem 7.4 consists of a finite field with and , a length , an matrix over with a flag (the code is the row space of if holds, and otherwise), forbidden values and a precision . Let . A field element is stored as its coordinate list in the power basis, and denotes the entrywise coordinate matrix of a matrix .
The quantum program is produced by a generator that works only with natural numbers and lists (first-order "twins" of the mathematical constructions). From the parsed input record and an input length it computes the record of derived numbers. These are , , the coefficients of , , , the coordinate lists of the entries of , the bit blocks of , , , , the saturated field size and the search budget .
The mathematical construction uses a basis of that is the identity on a set of pivot columns: the reduced row echelon rows of when is false, and the standard null-space basis of when is true. Here is denoted . The generator computes the same number as , by Gaussian elimination on coordinate lists in which field inverses are found by a search bounded by .
Statement. If , then
The generator branches on this number: it outputs the trivial classical program if and the quantum program otherwise. The number also enters the sizes of the wire layout. The lemma is used throughout the proof that the generator outputs exactly the serialization of the intended program.
import Definitions.Def_TwoFoldOPI_CL_Part05 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.Gen open QAlgorithms QAlgorithms.OPI TwoFoldOPI Lay TD RRefC FM SymEnc variable (x : Input) (n : ℕ) (hq : x.F.p ^ x.F.f.natDegree ≤ n) include hq
theorem OPI.Gen.kdN_eq : kdN (numsOf n (parsedOf x)) = kdOf x.F x.m x.gen x.H := by sorry