A chain of repeat-until-success stages as a preparation law
ProvedOPI.PreLaw.rusChainA preparation law for a program transformer says the following: whenever a continuation , started from the vector , produces a given output event with probability at least for every classical memory, then started from produces it with probability at least .
A repeat-until-success job consists of a register of system qubits and a membership test on bit patterns. Its success factor is the unnormalised state on . Each attempt applies Hadamards to , computes the test into a flag (using ancillas and ), and measures the flag. On failure it resets and retries, and after failed attempts the program fails. Let run the jobs of a list in order, then the continuation. The system has qubits next to a -qubit gradient register.
Statement. Assume each job's register together with , and is duplicate-free with , the job registers are pairwise disjoint, and vanishes unless all job registers, , and are . Then for every state of the gradient register,
where the job factors are placed on their registers, and with the failure probability of one attempt.
Since , each job contributes a success probability . This lemma composes all preparation jobs (pivots, resources, registers) into one law.
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
open QAlgorithms
variable {n b c out : ℕ} {event : Option (Fin out → Bool) → Prop}
theorem OPI.PreLaw.rusChain (fl f0 : Fin n) (as : List (Fin n)) (dst : Fin c) (R : ℕ) :
∀ (js : List (RJob n)), (∀ j ∈ js, (List.ofFn j.w ++ [fl] ++ as ++ [f0]).Nodup ∧ j.k ≤ as.length + 2) →
(js.map RJob.res).Pairwise Res.Disj →
∀ (f : Qubits n → ℂ) (γ : Qubits b → ℂ),
(∀ z, f z ≠ 0 → (∀ j ∈ js, ∀ i, z (j.w i) = false) ∧ z fl = false ∧ (∀ a ∈ as, z a = false) ∧
z f0 = false) →
PreLaw event (rusChain (b := b) (c := c) (out := out) fl f0 as dst R js) (tens f γ)
(tens (bfacL (js.map RJob.res) f) γ) ((js.map fun j => RJob.wt (b := b) j R).prod) 0 := by sorry