Fixed-width binary expansion has a polynomial realizer
ProvedOPI.W6.IsPR.natBits_prlean-formalizationquantum-algorithmstwo-fold-opi-construction
For natural numbers , is the list of the binary digits of , most significant bit first.
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.
Binary expansions appear in the entries of the lookup tables of the circuit (phase tables, controlled-rotation tables, encodings of coordinates), so the generator needs this realizer to output those tables.
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
variable {α : Type} [Coding α]
Formal statement
theorem OPI.W6.IsPR.natBits_pr : IsPR (fun x : ℕ × ℕ => natBits x.1 x.2) := by sorry
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/f7224a159e790347c1a83c5ac23c63e5094a6a2c/WorkInProgress/QuantumOPIVariants/OPI/BitsPR.lean#L135-L145