Uniform valid symbols on the pivot registers equal a sum over pivot words
ProvedOPI.SymEnc.pivRes_sumlean-formalizationquantum-algorithmstwo-fold-opi-construction
Let the word register consist of symbol registers of qubits each, with pairwise distinct wires. Let be injective. A bit pattern of length is valid if each of its blocks encodes a number , i.e. for some field element . For let be the word with at coordinate and elsewhere, and its encoding on .
Let , and let be a vector on the whole system that vanishes unless all of is .
Statement. Placing the factor on each pivot register of gives
The repeat-until-success stage on the pivot registers thus prepares the uniform superposition over all words supported on the pivot coordinates. The reversible linear map , with an RREF basis of , then sends it to the uniform superposition over without an extra coefficient register.
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
variable {N : ℕ}
open TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n m kd : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
(piv : Fin kd → Fin m) (hpivi : Function.Injective piv)
open Classical
include hRd hpivi
Formal statement
theorem OPI.SymEnc.pivRes_sum (c0 : ℂ) (G0 : Qubits n → ℂ)
(hG0 : ∀ z, G0 z ≠ 0 → z ∘ wRof (F := F) Rr hRd = fun _ => false) :
bfacL (pivRes Rr piv (fun v => if Fq.Valid F v then c0 else 0)) G0 =
∑ a : Fin kd → F.F, c0 ^ kd • bfac (wRof (F := F) Rr hRd)
(fun y => if y = encW F m (vPiv piv a) then 1 else 0) G0 := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/PrepState.lean#L136-L244