Failure bound for the repeated trial loop on the concrete qubit layout
ProvedOPI.Lay.trial_concreteLet be an explicitly presented finite field with , prime characteristic , and defining polynomial . Let be the code given by an matrix (its row space if gen, its kernel otherwise), and let . Let be the forbidden values and . Let be the precisions of the QFT resources and of the -qubit gradient register.
The program trialsC runs at most trials on the concrete wire layout. Each trial prepares the state, with repeat-until-success attempts per job. It then applies the decoder circuit , the subtraction and , and tests whether the register is zero. On acceptance it measures the symbol registers into injectively chosen classical slots and outputs those bits. On rejection it resets the system and tries again.
Put , and . Let be the preparation weight. Assume , and . Assume also that the event contains every output whose decoded word lies in . Then, starting from with any classical memory,
This is the main correctness bound for the quantum branch of the algorithm before the parameters are chosen. The final theorem chooses them so that the right-hand side is at most .
import Definitions.Def_TwoFoldOPI_CL_Part04
import Definitions.Def_TwoFoldOPI_solves
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_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI OPI.Lay
open QAlgorithms TwoFoldOPI RelinProg SymEnc GEP
variable (F : AvgCaseTI.FieldPres) (m t b : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
local notation "KD" => kdOf F m gen H
local notation "nI" => SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)
local notation "PP" => parOf F m t b (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H))
local notation "NN" => total (parOf F m t b (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
variable (ht : 1 ≤ t) (htb : t ≤ b)
open Classical
theorem OPI.Lay.trial_concrete (hq : 2 ≤ Fintype.card F.F) (hp : 0 < F.p) (β : Fin m → F.F) {c : ℕ}
(dz dst : Fin c) (slot : Fin (m * bitsPerSymbol F) → Fin c) (hslot : Function.Injective slot)
(event : Option (Fin (m * bitsPerSymbol F) → Bool) → Prop)
(hev : ∀ bits, decodeWord F m bits ∈ codeOf gen H ∧ decodeWord F m bits ∈ targetSet β → event (some bits))
(R : ℕ) (w e : ℝ) (hw0 : 0 < w) (hw1 : w ≤ 1)
(hw : w ≤ (prepC F m t b gen H ht htb).W β R *
(Complex.normSq (cAll (decC F m t b gen H ht htb).D KD) * (Dfin gen H).card))
(he : 2 * (m * (2 * Real.pi / 2 ^ b)) * ((prepC F m t b gen H ht htb).W β R *
(Complex.normSq (cAll (decC F m t b gen H ht htb).D KD) * (Dfin gen H).card)) ≤ e)
(hP : 0 < decP F b t m (schurFailureSum (CodingTheory.dualCode F.F (Fin m) (codeOf gen H))))
(K : ℕ) (mem : Fin c → Bool) :
1 - lawP (trialsC F m t b gen H ht htb β dz dst slot hslot R K) event
(tens (sysZero NN) (gradVec b)) mem ≤
(1 - w + w * ((Dfin gen H).card *
(1 - decP F b t m (schurFailureSum (CodingTheory.dualCode F.F (Fin m) (codeOf gen H))))) + e) /
(w * decP F b t m (schurFailureSum (CodingTheory.dualCode F.F (Fin m) (codeOf gen H)))) +
(1 - w * decP F b t m (schurFailureSum (CodingTheory.dualCode F.F (Fin m) (codeOf gen H)))) ^ K := by sorry