Error of the gadget:
ProvedOPI.QQ.errlean-formalizationquantum-algorithmstwo-fold-opi-construction
Let , , be given by a field presentation, with symbols encoded on qubits (power-basis coordinates in blocks of bits). A gadget consists of:
- a symbol register of qubits;
- gadgets whose data registers are the blocks of , pairwise compatible and sharing one clean set , each with resource register and control register ;
- a reversible re-encoding with scratch inside , which maps the power-basis encoding of to its trace-dual coordinates .
Its system unitary is . Let be the QFT over on symbols, on valid symbols with , and .
Statement. Assume and . Let satisfy, on its support: holds a valid symbol, the re-encoding scratch is clean, and for every the registers , are and its accumulator and scratch are clean. Then
The decoder applies this gadget to both symbols of every coordinate. The bound enters its total error, of order .
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.QQ
open QAlgorithms TwoFoldOPI Matrix
variable {n b : ℕ}
variable {F : AvgCaseTI.FieldPres} {t : ℕ} (Q : QQ n b F t)
Formal statement
theorem OPI.QQ.err (hp : 0 < F.p) (ht : 1 ≤ t) (g : Qubits n → ℂ)
(hg : ∀ z, g z ≠ 0 → Fq.Valid F (z ∘ Q.X) ∧ Q.RC z ∧
∀ G ∈ Q.Gs, z ∘ G.bE = (fun _ => false) ∧ z ∘ G.cE = (fun _ => false) ∧ G.C z) :
vnorm (Q.U.mulVec (QG.prepAll Q.Gs g) - (embedOp (Fq.Qq F) Q.X).mulVec g) ≤
F.f.natDegree * (2 * Real.pi / 2 ^ b + 2 * (F.p / Real.sqrt (2 ^ t))) * vnorm g := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/QFTqGad.lean#L247-L295