The generator's repeat-until-success jobs are the intended ones
ProvedOPI.Gen.jobs_eqSetting. An instance of the two-fold OPI problem of Theorem 7.4 consists of a finite field (, , , bits per symbol), a length , a matrix with a flag defining a code , forbidden values and a precision . Let , with basis pivots .
The state preparation of the quantum program uses repeat-until-success jobs. A job is a list of wires together with a lookup table (a list of pairs of bit patterns) that decides acceptance. The full job list has three kinds of entries:
- a pivot job for each pivot , where accepts an -bit pattern iff it encodes a field element;
- a resource job for each resource wire list , where accepts a -bit pattern iff its value is ;
- an -job for each , where accepts an -bit pattern iff it encodes a field element different from .
The generator works only with natural numbers and lists. From the parsed input and an input length it forms and the layout tuple , from which the registers , the resource wires and the symbol registers are computed. is the job list it builds. In it, the pivots are its own pivot list, and the tables are first-order tables enumerated up to the budget .
Statement. If , then the job list built from the generator's wires, the true pivot list and the mathematically defined tables , , equals .
This identifies the preparation part of the generated program with the intended one, as part of the proof that the generator outputs the serialization of the constructed 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 local notation "vl" => List.map Fin.val variable (x : Input) (n : ℕ) (hq : x.F.p ^ x.F.f.natDegree ≤ n) include hq local notation "u" => numsOf n (parsedOf x) local notation "KD" => kdOf x.F x.m x.gen x.H
theorem OPI.Gen.jobs_eq :
allJobsN ((List.range x.m).map (RrN (XN (numsOf n (parsedOf x))))) (pivW (basisOf x.gen x.H).piv)
(resAllX (XN (numsOf n (parsedOf x)))) ((List.range x.m).map (fun i => bRegN (XN (numsOf n (parsedOf x))) i 0))
(TpF x.F) (TrF x.F) (TsF x.F x.β) = jobsN (numsOf n (parsedOf x)) := by sorry