With polynomial parameters the quantum program fails with probability at most
ProvedOPI.Lay.final_boundlean-formalizationquantum-algorithmstwo-fold-opi-construction
Let be a presented finite field with elements and qubits per symbol, an matrix over , and a flag. The code is the row space of (if ) or its kernel, , , and , which is assumed to be (so ). Let be the forbidden values and .
For a security parameter put . The program is with
- gradient width and precision ,
- repeat-until-success cap , where is the number of repeat-until-success jobs,
- trials,
- majority tests per gradient bit.
Let "event" be any property of the output that holds whenever the output bits decode to a word of .
Statement. Started from the all-zero state, with any initial classical memory,
This is the formal version of the success guarantee of Theorem 7.4 for . All parameters are polynomial in , and , so the program has polynomial size.
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.Lay
open QAlgorithms TwoFoldOPI
open SymEnc
variable (F : AvgCaseTI.FieldPres) (m : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F) (T : ℕ)
local notation "LL" => bitsPerSymbol F
local notation "BB" => Bpar T m (bitsPerSymbol F)
local notation "KD" => kdOf F m gen H
local notation "NNf" => total (parOf F m (2 * Bpar T m (bitsPerSymbol F)) (2 * Bpar T m (bitsPerSymbol F) - 1 + 1)
(SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
set_option maxHeartbeats 2000000
open Classical
Formal statement
theorem OPI.Lay.final_bound (hq : 2 ≤ Fintype.card F.F) (hkd : 1 ≤ KD) (β : Fin m → F.F) {c : ℕ} (dG dz dst : Fin c)
(slot : Fin (m * LL) → Fin c) (hslot : Function.Injective slot)
(event : Option (Fin (m * LL) → Bool) → Prop)
(hev : ∀ bits, decodeWord F m bits ∈ codeOf gen H ∧ decodeWord F m bits ∈ targetSet β → event (some bits))
(mem : Fin c → Bool) :
1 - lawP (progFinal F m gen H T β dG dz dst slot hslot) event (sysZero (NNf + (2 * BB - 1 + 1))) mem ≤
2 * (Dfin gen H).card * schurFailureSum (CodingTheory.dualCode F.F (Fin m) (codeOf gen H)) + (1 / 2) ^ T := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/FinalBound.lean#L74-L248