Precision of the gadgets: for
ProvedOPI.epsQ_lelean-formalizationquantum-algorithmstwo-fold-opi-construction
Let be a presented finite field with at least elements, and let be the number of qubits per symbol. A gadget built with a -qubit phase-gradient register and -bit phase estimation has error at most
For put .
Statement.
With this choice of , the total error of the gadgets in the real decoder stays below , even after multiplying by . This step of the final bound final_bound is where the gradient width is fixed.
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 open QAlgorithms TwoFoldOPI
Formal statement
theorem OPI.epsQ_le (F : AvgCaseTI.FieldPres) (hq : 2 ≤ Fintype.card F.F) (T m : ℕ) :
SymEnc.epsQ F (2 * Bpar T m (bitsPerSymbol F)) (2 * Bpar T m (bitsPerSymbol F)) ≤
(1 / 2) ^ (T + m + m * bitsPerSymbol F + 7) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/FinalNum.lean#L268-L316