Blockwise after trace-dual re-encoding equals
ProvedOPI.Fq.prod_qftPlean-formalizationquantum-algorithmstwo-fold-opi-construction
Let with and , and let . A field element is encoded on qubits by : block () holds, in binary, the -th coordinate of in the power basis . Let and let be the canonical additive character. Two matrices enter:
- for -bit strings with values , and otherwise;
- if both symbols are valid (every block ), and otherwise.
Statement. For every bit string of length , with blocks , and every ,
In words: if the input symbol is first re-encoded from power-basis coordinates to its trace-dual coordinates , then applying to each block yields exactly the QFT over in the power-basis encoding. This is how the gadget is built from gadgets and one reversible re-encoding.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part01 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.Fq open QAlgorithms TwoFoldOPI Matrix variable (F : AvgCaseTI.FieldPres)
Formal statement
theorem OPI.Fq.prod_qftP (z : Qubits (bitsPerSymbol F)) (x : F.F) :
∏ j, qftP F.p (w F) (z ∘ blk F j) (natToBits (w F) (sco F x j).val) =
Qq F z (elemBits F x) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/QFTq.lean#L229-L279