The Theorem 7.4 construction is Cook–Levin serializable on raw prefixes
ProvedOPI.Gen.constructQ_CLSetting. An instance of the two-fold OPI problem of Theorem 7.4 consists of a finite field with elements, a length , an matrix over with a flag defining a code , forbidden values and a precision . It has a public bit encoding and size parameter . The construction is the packed program of the theorem: a trivial classical program if , and otherwise the quantum Regev-style program (phase-gradient preparation followed by repeated trials of state preparation, decoding of by Schur-square relinearization, and measurement).
A family of programs is Cook–Levin serializable on raw prefixes () if there are two Turing machines running in polynomial time in the Cook–Levin cost model, a decider computing and a generator computing , such that for every instance and every , with :
- , and
- if and , then .
Statement. is Cook–Levin serializable on raw prefixes.
This is the uniformity (polynomial-time constructibility) part of the algorithmic statement of Theorem 7.4.
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.constructQ_CL : CLSerializableF Leaf.constructQ := by sorry