Budgeted enumeration of all coordinate vectors in has a polynomial realizer
ProvedOPI.W6.IsPR.allLB_prlean-formalizationquantum-algorithmstwo-fold-opi-construction
For natural numbers , is the list of all lists of length with entries in (there are of them). The budgeted version is
means that has a polynomial realizer: a program of the underlying machine model whose running charge and output size are bounded by a monotone polynomial in the input size, where a natural number has size (unary coding).
Statement. The map has a polynomial realizer.
The budget is essential: without it the output has entries, which is exponential in the input size. The enumeration is used for brute-force search over the elements of (each element being a coordinate vector), namely field inversion and the inverse re-encoding table. Since the generator's budget dominates , the search is the full one.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part03
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.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.FM
variable {α : Type} [Coding α]
Formal statement
theorem OPI.W6.IsPR.allLB_pr : IsPR (fun x : ℕ × ℕ × ℕ => allLB x.1 x.2.1 x.2.2) := by sorry
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/f7224a159e790347c1a83c5ac23c63e5094a6a2c/WorkInProgress/QuantumOPIVariants/OPI/FTablesPR.lean#L293-L334