On every padded prefix of the encoding, the generator outputs the serialization of the construction
ProvedOPI.Gen.gen_specSetting. An instance of the two-fold OPI problem of Theorem 7.4 consists of a finite field , a length , an matrix with a flag defining a code , forbidden values and a precision . Its public encoding lists the field, , , , the entries of and of (as bit blocks) and . Its size parameter is , where . The construction is the packed program of Theorem 7.4: a trivial classical program if , and the quantum Regev-style program otherwise. is its canonical bit-string serialization.
The generator reads a bit string , parses it (with numbers saturated at ) and runs the natural-number construction with input length .
Statement. Let with and , and let be the encoding padded with zeros to length exactly . Then
This is the correctness half of the Cook–Levin serializability of the construction. Raw zero-padded prefixes are the inputs on which the uniformity notion runs its machines.
import Definitions.Def_TwoFoldOPI_CL_Part05 import Definitions.Def_TwoFoldOPI_CLSerializableF 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 open OPI OPI.Gen open QAlgorithms QAlgorithms.OPI TwoFoldOPI
theorem OPI.Gen.gen_spec (x : Input) (s : ℕ) (h1 : x.encode.length ≤ s) (h2 : x.scale ≤ s) :
gen ((x.encode ++ List.replicate s false).take s) = packedSerialization (Leaf.constructQ x) := by sorry