The quantum program's first-order segment equals the generated segment
ProvedOPI.Gen.quantSeg_GSetting. 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 and .
Programs are represented by first-order DAGs, which are lists of nodes (tag, fields, children). A segment is a function that, given a continuation node index and a start position , returns the list of new nodes to append at positions . The quantum program for is given by the segment . It prepares the phase-gradient state and then runs a retry loop of trials, each consisting of state preparation, trial circuit and measurement. The parameters are fixed: precision and gradient width ; the classical cells used by the gradient preparation, by the trial flag and by the state preparation are all the last memory cell (index ); the output bits go to the first memory cells; repeat-until-success cap , where is the number of jobs; trials; and majority tests for the gradient.
The generator works only with natural numbers and lists. From the parsed input and an input length it forms and the segment .
Statement. If , then
as functions lists of nodes.
This lemma is used to show that the DAG produced by the generator represents the intended quantum 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 set_option maxHeartbeats 1000000
theorem OPI.Gen.quantSeg_G :
quantSeg x.F x.m (2 * Bpar x.t x.m (bitsPerSymbol x.F)) (2 * Bpar x.t x.m (bitsPerSymbol x.F) - 1) x.gen x.H
(tB_pos x.F x.m x.t) (tB_le x.F x.m x.t) x.β (Fin.last _) (Fin.last _) (Fin.last _) Fin.castSucc
(Rpar x.F x.m x.gen x.H x.t x.β) (x.t + 3) (2 * x.t + 6 + (2 * Bpar x.t x.m (bitsPerSymbol x.F) - 1)) =
qSegG (numsOf n (parsedOf x)) := by sorry