The ideal relinearization decoder succeeds with probability at least
ProvedOPI.DecProb.decode_prob_gelean-formalizationquantum-algorithmstwo-fold-opi-construction
Let be a finite field with elements, a linear code spanned by vectors , and its Schur square (the span of coordinatewise products), spanned by . Let
where is the zero set of and denotes shortening on .
For , is the probability of observing the ordered pair when measuring in the computational basis: if exactly one of equals , and otherwise. The decoder uses Gauss–Jordan elimination to find a solution , , , of the relinearized system , and returns .
Statement. For every ,
where . That is, measuring and decoding the symmetric functions , recovers with probability at least . This is the ideal decoding guarantee that the real decoder's analysis perturbs.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part01
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.DecProb
open TwoFoldOPI
variable {K : Type*} [Field K] [Fintype K] [DecidableEq K] {m : ℕ}
Formal statement
theorem OPI.DecProb.decode_prob_ge (hK : 2 ≤ Fintype.card K) {k k2 : ℕ} (bD : Fin k → Fin m → K)
(bW : Fin k2 → Fin m → K) {D : Submodule K (Fin m → K)}
(hD : Submodule.span K (Set.range bD) = D) (hW : Submodule.span K (Set.range bW) = schurSquare D)
(d : Fin m → K) (hd : d ∈ D) :
1 - schurFailureSum D ≤
∑ z : Fin m → K × K, (∏ i, wPair (d i) (z i)) *
(if Relin.decode bD bW (fun i => (z i).1 + (z i).2) (fun i => (z i).1 * (z i).2) = d
then 1 else 0) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/DecProb.lean#L129-L180