Factor-wise preparation of the registers yields a symbol-level product state
ProvedOPI.SymEnc.sRes_Jlean-formalizationquantum-algorithmstwo-fold-opi-construction
Field symbols are written on qubits by the injective encoding . An embedding places the symbol pairs on qubits of an -qubit system. For a function on tuples , , where writes of each component into its register and on every other qubit.
Let be a vector on the qubits of , for , supported on encodings: implies for some .
Statement. Placing the factor on each register of the all-zero state gives
The qubit state equals the image under of the symbol-level product state .
This connects the qubit-level outcome of the repeat-until-success stages on the registers with the symbol-level description used by the decoder analysis. There, is the uniform superposition over .
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part02
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.SymEnc
open QAlgorithms TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n m : ℕ} (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)
open Classical
Formal statement
theorem OPI.SymEnc.sRes_J (h : Fin m → Qubits (bitsPerSymbol F) → ℂ)
(hs : ∀ i v, h i v ≠ 0 → ∃ y, elemBits F y = v) :
bfacL (sRes reg h) (sysZero n) = J reg (elemBits F) (prodF (sProd h)) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/PrepJ.lean#L35-L122