When , the generator outputs the serialization of the quantum program
ProvedOPI.Gen.genOut_quantSetting. 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 trivial classical program if . Otherwise it is the quantum program: preparation of a phase-gradient state, followed by at most trials of the Regev-style reduction, with fixed polynomial parameters. A packed program has a canonical bit-string serialization , consisting of its header (oracle count, qubits, classical bits, output bits) and its program tree as a table of hash-consed nodes.
The generator works only with natural numbers and lists. From the parsed input record and an input length it forms the derived numbers and outputs . This output is the serialization of the bottom program if . Otherwise it is the serialization of a first-order DAG: a node followed by the nodes of the generated quantum segment , with a header computed from .
Statement. If and , then
Together with the corresponding statement for , this shows that the generator outputs the serialization of the construction on every parsed instance.
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 set_option maxHeartbeats 1000000
theorem OPI.Gen.genOut_quant (h : kdN (numsOf n (parsedOf x)) ≠ 0) :
genOut n (parsedOf x) = packedSerialization (Leaf.constructQ x) := by sorry