Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The trial loop with the concrete decoder and subtraction succeeds with geometric-sum probability

Proved
OPI.SymEnc.trials_dec

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

lean-formalizationquantum-algorithmstwo-fold-opi-construction

Setting: K=FqK=\mathbb F_qK=Fq​, mmm coordinates, and nnn system qubits plus a bbb-qubit gradient register in ∣Gb⟩|G_b\rangle∣Gb​⟩. A full decoder layout XXX provides, for forbidden values β∈Km\beta\in K^mβ∈Km, a basis bDbDbD of DDD and a spanning set bWbWbW of D∗2D^{*2}D∗2, a decoder circuit CdC_dCd​ and its unitary UUU. CdC_dCd​ consists of the per-coordinate gadgets (y↦βi−yy\mapsto\beta_i-yy↦βi​−y, the gadget EEE, two QFTq\mathrm{QFT}_qQFTq​ gadgets) followed by the compiled relinearization decoder. XXX also provides a common clean set clclcl and a register RRR of mLmLmL qubits, split into blocks R1,…,RmR_1,\dots,R_mR1​,…,Rm​. Let OiO_iOi​ be the decoder's output register for coordinate iii, and let out(z)∈Km\mathrm{out}(z)\in K^mout(z)∈Km be the decoded content of the OiO_iOi​. The circuit CsC_sCs​ performs Ri←Ri−OiR_i\leftarrow R_i-O_iRi​←Ri​−Oi​ for all iii, with scratch ZsZsZs, asasas, fsfsfs. The layout hypotheses say: these wires are distinct, have the right sizes, and avoid RRR where needed; the scratch lies in clclcl; clclcl and the OiO_iOi​ avoid RRR.

Let D⊆KmD\subseteq K^mD⊆Km be finite and let ψd\psi_dψd​ be vectors with R=0R=0R=0. Put Ψ=∑d∈D∣d⟩R⊗ψd\Psi=\sum_{d\in D}|d\rangle_R\otimes\psi_dΨ=∑d∈D​∣d⟩R​⊗ψd​, and assume it vanishes unless clclcl is clean. A trial runs a preparation pre\mathrm{pre}pre, then CdC_dCd​, CsC_sCs​, Cd−1C_d^{-1}Cd−1​, then measures the qubits of RRR one by one. If all are 000, it measures the readout qubits qSqSqS into memory and halts with them as output. Otherwise it resets all system qubits and continues. retryK\mathrm{retry}_KretryK​ performs at most KKK trials and then fails. The preparation is assumed to reach Ψ⊗∣Gb⟩\Psi\otimes|G_b\rangleΨ⊗∣Gb​⟩ with weight www and loss eee: any continuation with law ≥κ\ge\kappa≥κ from Ψ⊗∣Gb⟩\Psi\otimes|G_b\rangleΨ⊗∣Gb​⟩ has law ≥wκ−e\ge w\kappa-e≥wκ−e when preceded by pre\mathrm{pre}pre from ∣0n⟩⊗∣Gb⟩|0^n\rangle\otimes|G_b\rangle∣0n⟩⊗∣Gb​⟩.

Statement. With v=U†∑d∈DΠout=dUψdv=U^\dagger\sum_{d\in D}\Pi_{\mathrm{out}=d}U\psi_dv=U†∑d∈D​Πout=d​Uψd​, and Πbad\Pi_{\mathrm{bad}}Πbad​ the restriction to configurations whose readout bits fail the event,

(w(∥v∥2−∥Πbadv∥2)−e)∑j<K(w(∥Ψ∥2−∥v∥2))j≤Pr⁡[retryK outputs an event outcome],\Big(w\big(\|v\|^2-\|\Pi_{\mathrm{bad}}v\|^2\big)-e\Big)\sum_{j<K}\Big(w\big(\|\Psi\|^2-\|v\|^2\big)\Big)^j\le\Pr\big[\mathrm{retry}_K\ \text{outputs an event outcome}\big],(w(∥v∥2−∥Πbad​v∥2)−e)j<K∑​(w(∥Ψ∥2−∥v∥2))j≤Pr[retryK​ outputs an event outcome],

for every KKK and every initial memory, starting from ∣0n⟩⊗∣Gb⟩|0^n\rangle\otimes|G_b\rangle∣0n⟩⊗∣Gb​⟩.

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.

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
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
Formal statement
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
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/TrialInst.lean#L37-L96

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me