The generated DAG represents the constructed program
ProvedOPI.Gen.genDag_repSetting. An instance of the two-fold OPI problem of Theorem 7.4 consists of a finite field (, ), a length , a matrix with a flag defining a code , forbidden values and a precision . Let . The construction is a packed program with no oracles. It is a classical program writing a fixed solution if , and the quantum Regev-style program otherwise. For a program tree on qubits with classical bits and output bits, is the packed program with no oracles and these dimensions.
A first-order DAG is a list of nodes (tag, fields, list of children). means that node represents the program tree : its tag and fields are those of the root of , its children have smaller indices and represent the subprograms, and makes no oracle queries.
Before serialization, the generator outputs , computed with natural-number arithmetic from the parsed input and the input length .
Statement. If , there exist and a program with these dimensions such that
- ,
- the header is , and
- .
This is the form of correctness used for the resource bound. A polynomial bound on the size of the generated DAG bounds the resources 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
theorem OPI.Gen.genDag_rep : ∃ (N c out : ℕ) (P : Prog N c out),
Leaf.constructQ x = packP P ∧ (genDag n (parsedOf x)).1 = [0, N, c, out] ∧
Rep (genDag n (parsedOf x)).2.1 (genDag n (parsedOf x)).2.2 P := by sorry