The shared tables of the gadgets equal their budgeted first-order twins
ProvedOPI.TabSub.shOf_eqlean-formalizationquantum-algorithmstwo-fold-opi-construction
Let , , and the number of bits of a field symbol. A lookup table on -bit inputs is a list of pairs (pattern, output) over all patterns. The tuple collects the data shared by all gadgets of the circuit:
- : the tables of the re-encoding of a symbol from power-basis coordinates to trace-dual coordinates and of its inverse;
- : the phase table ( bits) on input bits;
- : the controlled-rotation tables of a -bit ;
- : for each wire of a control register, the pair of controlled-shift tables adding , respectively , modulo to a -bit value when the control bit is set;
- : the tables of and on bits.
In these tables are defined from functions on and enumerate all patterns unconditionally. Their first-order twins (, , , , , , ) compute the entries from and the coefficient list of , and enumerate the patterns only when (otherwise they output a dummy table).
Statement. For all with ,
This is the step that lets the generator, which works with a single pattern budget , output the tables required by the circuit specification.
Preamble
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 set_option autoImplicit false open QAlgorithms TwoFoldOPI FM W6 TD variable (F : AvgCaseTI.FieldPres)
Formal statement
theorem OPI.TabSub.shOf_eq (n b t N : ℕ) (hN : 2 ^ (2 * bitsPerSymbol F + 1) ≤ N) :
SymEnc.shOf F n b t =
(n, b, F.p, rlTabN F.p F.f.natDegree (Fq.w F) (flOf F) (bitsPerSymbol F) 0 N,
rlinvTabN F.p F.f.natDegree (Fq.w F) (flOf F) (bitsPerSymbol F) 0 N,
phaseTabN F.p (Fq.w F) b N, qftTabsN b t, csTabsN F.p (Fq.w F) t N,
subTabN F.p (Fq.w F) (Fq.w F + 1 + Fq.w F) (Fq.w F + 1) N,
addTabN F.p (Fq.w F) (Fq.w F + 1 + Fq.w F) (Fq.w F + 1) N) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/f7224a159e790347c1a83c5ac23c63e5094a6a2c/WorkInProgress/QuantumOPIVariants/OPI/TabSub.lean#L52-L67