The generator before serialization has a polynomial realizer
ProvedOPI.Gen.genD_PRSetting. The quantum program of Theorem 7.4 (for an instance consisting of a finite field , a matrix with a flag defining a code , forbidden values and a precision ) is produced by a generator that works only with natural numbers, booleans and lists. Its unserialized part is
It parses the bit string , computes the derived numbers of the instance (field data, basis of by first-order Gaussian elimination, lookup tables up to a budget , wire layout), and returns a header, a first-order program DAG and the index of its root.
A polynomial realizer of a function between encodable types consists of three things: a program of the underlying stack machine that computes on encodings; a monotone function with for some constants ; and the bounds that, on every input , both the running time and the volume (encoded size) of are at most .
Statement. has a polynomial realizer, i.e. is nonempty.
The volume bound is what the resource bound of Theorem 7.4 uses. The size of the generated DAG, and hence the number of qubits, classical bits and nodes of the constructed program, is polynomial in .
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
theorem OPI.Gen.genD_PR : Nonempty (W6.PR genD) := by sorry