Failure bound for the trial loop with the concrete preparation and decoder
ProvedOPI.SymEnc.trial_alglean-formalizationquantum-algorithmstwo-fold-opi-construction
Let be a presented finite field with elements, each symbol stored in qubits, and let be a linear code, spanned by vectors , whose Schur square is spanned by . The data are:
- a full decoder layout on system qubits and a -qubit gradient register: per coordinate the gadgets (), , and two gadgets of precision consuming resource states, followed by the compiled relinearization decoder whose output registers hold the decoded word; is the resulting system unitary;
- a preparation layout with a matrix (identity on pivot columns, injective) whose image is the finite set ;
- wire-disjointness hypotheses making a valid reversible subtraction on clean scratch;
- readout wires copied into distinct memory slots, and an event on outputs that holds on every basis configuration in the support of of the ideal per-word states (resources the symbol state );
- reals below the preparation weight and above its phase-error term.
Let , and , assumed . The program runs at most trials (prepare; ; ; ; measure ; accept and read out, or reset and retry) from . Then
This assembles preparation, decoder, subtraction and trial loop into one bound; the final theorem instantiates it with concrete parameters.
Preamble
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 CoordSym
variable {F : AvgCaseTI.FieldPres} {n b t m k k2 : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable {reg : Fin m × Bool × Fin L ↪ Fin n}
open Classical
Formal statement
theorem OPI.SymEnc.trial_alg (hq : 2 ≤ Fintype.card F.F) (hp : 0 < F.p) (ht : 1 ≤ t) {kd : ℕ}
(X : DecFull F reg b t k k2 (m * L)) (Pl : PrepLay X.D kd) (hwR : X.wR = wRof (F := F) Pl.Rr Pl.hRd)
(β : Fin m → F.F) (bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F)
{Dc : Submodule F.F (Fin m → F.F)} (hD : Submodule.span F.F (Set.range bD) = Dc)
(hW : Submodule.span F.F (Set.range bW) = schurSquare Dc)
(Ds : Finset (Fin m → F.F)) (hDsD : ∀ d, d ∈ Ds ↔ d ∈ Dc)
(hDs : ∀ d, d ∈ Ds ↔ ∃ a, Matrix.vecMul a Pl.G = d)
(hGi : Function.Injective fun a : Fin kd → F.F => Matrix.vecMul a Pl.G)
-- the subtraction layout
(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 (Pl.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'), Pl.Rr i j ≠ q)
(hsc : ∀ (i : Fin m) j, Pl.Rr i j ≠ fs ∧ (∀ q ∈ Zs, Pl.Rr i j ≠ q) ∧ ∀ q ∈ as, Pl.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)
(hclQoff : ∀ q ∈ X.clQ, (∀ p, reg p ≠ q) ∧ ∀ r ∈ resAll X.D, q ∉ Set.range r.w)
-- the readout and the event
{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)
(hgood : ∀ z : Qubits n, (∑ d ∈ Ds, RSall X.D (J reg (elemBits F) (prodF (g0 (F := F) β d)))) z ≠ 0 →
event (some fun j => z (qS j)))
(dst : Fin c) (R : ℕ) (w e : ℝ) (hw0 : 0 < w) (hw1 : w ≤ 1)
(hw : w ≤ Pl.W β R * (Complex.normSq (cAll X.D kd) * Ds.card))
(he : 2 * (m * (2 * Real.pi / 2 ^ b)) * (Pl.W β R * (Complex.normSq (cAll X.D kd) * Ds.card)) ≤ e)
(hP : 0 < decP F b t m (schurFailureSum Dc)) (K : ℕ) (mem : Fin c → Bool) :
let Os := fun i : Fin m => X.C.rs (RelinProg.outId (m := m) (k := k) (k2 := k2) i)
let Cs := revCirc (subAll (F := F) Pl.Rr Os Zs as fs (List.finRange m))
let P := decP F b t m (schurFailureSum Dc)
1 - lawP (retry (trialStep (Pl.pre β dst R) (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 ≤
(1 - w + w * (Ds.card * (1 - P)) + e) / (w * P) + (1 - w * P) ^ K := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/Assemble.lean#L36-L153