The state after all repeat-until-success jobs of the preparation
ProvedOPI.SymEnc.rus_stateWork in the qubit layout of the algorithm: field symbols are written with qubits via the encoding . The registers are the symbol pairs , , the word register , and the resource registers of the QFT gadgets. Let be injective (pivot coordinates). Assume the wires are pairwise distinct and disjoint from the symbol registers and the resource registers, and .
The preparation runs three kinds of repeat-until-success jobs. On success, each job leaves an unnormalised factor on its register:
- each pivot register gets times the indicator of a valid symbol encoding;
- each resource register gets times the indicator of a value ;
- each gets times the indicator of "valid and ".
Statement. Applying all these factors to the all-zero state gives
Here is the word with at coordinate and elsewhere, and . embeds symbol-level states into qubits, and places the normalised resource states on all resource registers. The scalar is .
This identifies the output of the first preparation stage. It is uniform over the pivot coordinates of , which the linear map then turns into the uniform superposition over .
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 {n : ℕ}
variable {F : AvgCaseTI.FieldPres} {m kd : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable {b t : ℕ} {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)
open Classical
theorem OPI.SymEnc.rus_state (hq : 2 ≤ Fintype.card F.F) (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) (β : Fin m → F.F)
(hRreg : ∀ i j p, reg p ≠ Rr i j) (hRres : ∀ r ∈ resAll D, ∀ i j, Rr i j ∉ Set.range r.w) :
bfacL ((allJobs D Rr piv β).map RJob.res) (sysZero n) =
cAll D kd • ∑ a : Fin kd → F.F, bfac (wRof (F := F) Rr hRd)
(fun y => if y = encW F m (vPiv piv a) then 1 else 0) (RSall D (J reg (elemBits F) (prodF (gA β)))) := by sorry