The trial loop with the concrete decoder and subtraction succeeds with geometric-sum probability
ProvedOPI.SymEnc.trials_decSetting: , coordinates, and system qubits plus a -qubit gradient register in . A full decoder layout provides, for forbidden values , a basis of and a spanning set of , a decoder circuit and its unitary . consists of the per-coordinate gadgets (, the gadget , two gadgets) followed by the compiled relinearization decoder. also provides a common clean set and a register of qubits, split into blocks . Let be the decoder's output register for coordinate , and let be the decoded content of the . The circuit performs for all , with scratch , , . The layout hypotheses say: these wires are distinct, have the right sizes, and avoid where needed; the scratch lies in ; and the avoid .
Let be finite and let be vectors with . Put , and assume it vanishes unless is clean. A trial runs a preparation , then , , , then measures the qubits of one by one. If all are , it measures the readout qubits into memory and halts with them as output. Otherwise it resets all system qubits and continues. performs at most trials and then fails. The preparation is assumed to reach with weight and loss : any continuation with law from has law when preceded by from .
Statement. With , and the restriction to configurations whose readout bits fail the event,
for every and every initial memory, starting from .
This instantiates the abstract trial-loop theorem with the concrete decoder and subtraction circuits. Combined with the Regev numbers and the interference identity, it gives the success bound of the full algorithm.
import Definitions.Def_TwoFoldOPI_CL_Part04
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 b t m k k2 : ℕ}
{reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
open Classical
theorem OPI.SymEnc.trials_dec (hp : 0 < F.p) (X : DecFull F reg b t k k2 (m * L)) (β : Fin m → F.F)
(bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F)
(Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
(hwR : X.wR = wRof (F := F) Rr hRd) (Zs as : List (Fin n)) (fs : Fin n)
(hnd : ∀ i : Fin m, (X.C.rs (RelinProg.outId (m := m) (k := k) (k2 := k2) i) ++ List.ofFn (Rr i) ++ Zs ++ as ++
[fs]).Nodup) (hZ : L = Zs.length)
(hlen : ∀ i : Fin m, (X.C.rs (RelinProg.outId (m := m) (k := k) (k2 := k2) i)).length + L ≤ as.length + 2)
(hOs : ∀ (i i' : Fin m) j, ∀ q ∈ X.C.rs (RelinProg.outId (m := m) (k := k) (k2 := k2) i'), Rr i j ≠ q)
(hsc : ∀ (i : Fin m) j, Rr i j ≠ fs ∧ (∀ q ∈ Zs, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)
(hsubcl : ∀ q, q ∈ Zs ∨ q ∈ as ∨ q = fs → q ∈ X.clQ)
(hclR : ∀ q ∈ X.clQ, q ∉ Set.range X.wR)
(hOsR : ∀ i : Fin m, ∀ q ∈ X.C.rs (RelinProg.outId (m := m) (k := k) (k2 := k2) i), q ∉ Set.range X.wR)
(D : Finset (Fin m → F.F)) (ψ : (Fin m → F.F) → Qubits n → ℂ)
(hcl : ∀ x, (∑ d ∈ D, bfac X.wR (delta (encW F m d)) (ψ d)) x ≠ 0 → ∀ a ∈ X.clQ, x a = false)
(hψ0 : ∀ d, projReg X.wR (fun _ => false) (ψ d) = ψ d) {c out : ℕ} (dz : Fin c)
(qS : Fin out → Fin n) (slot : Fin out → Fin c) (hslot : Function.Injective slot)
(event : Option (Fin out → Bool) → Prop)
(pre : Prog (n + b) c out → Prog (n + b) c out) (w e : ℝ)
(hpre : ∀ P' K, (∀ mem, K ≤ lawP P' event
(tens (∑ d ∈ D, bfac X.wR (delta (encW F m d)) (ψ d)) (gradVec b)) mem) →
∀ mem, w * K - e ≤ lawP (pre P') event (tens (sysZero n) (gradVec b)) mem)
(K : ℕ) (mem : Fin c → Bool) :
let Os := fun i : Fin m => X.C.rs (RelinProg.outId (m := m) (k := k) (k2 := k2) i)
let U := X.U β bD bW
let hout : ∀ z y, outOf (F := F) Os (setE X.wR z y) = outOf Os z := outOf_setE X.wR Os hOsR
let Cs := revCirc (subAll (F := F) Rr Os Zs as fs (List.finRange m))
(w * (nsq (vAcc U D ψ (outOf Os)) - nsq (offGood (fun z => event (some fun j => z (qS j)))
(vAcc U D ψ (outOf Os)))) - e) *
∑ j ∈ Finset.range K,
(w * (nsq (∑ d ∈ D, bfac X.wR (delta (encW F m d)) (ψ d)) - nsq (vAcc U D ψ (outOf Os)))) ^ j ≤
lawP (retry (trialStep pre (X.circ β bD bW ++ relocCirc sysEmb Cs ++ invCirc (X.circ β bD bW)) dz
(List.ofFn X.wR)
(measAll (readList (fun j => Fin.castAdd b (qS j)) slot)
(.halt (copyCirc slot) (copyCirc_wf slot)))) K) event (tens (sysZero n) (gradVec b)) mem := by sorry