Regev numbers: accepted mass , bad accepted mass
ProvedOPI.regev_boundsLet be a unitary on qubits (the decoder) and a finite nonempty set of labels. For each let be a unit vector, and let assign a label to every computational basis state (the value of the decoder's output register). Let be a real number such that, for every , the decoder recovers from with probability at least :
Let be a set of basis states such that vanishes outside (the interference condition).
Put and define the accepted vector
Statement.
where restricts to basis states outside .
In the algorithm, is the state accepted by one trial of Regev's reduction: decode, subtract the decoded word from , undecode, and test . The first inequality bounds the acceptance probability from below. The second bounds the probability of accepting with an output outside .
import Definitions.Def_TwoFoldOPI_CL_Part02
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 Matrix
variable {n : ℕ} {δ : Type*} [DecidableEq δ]
theorem OPI.regev_bounds (U : Mat n) (hU : U ∈ Matrix.unitaryGroup (Qubits n) ℂ) (D : Finset δ)
(hD : D.Nonempty) (ψ' : δ → Qubits n → ℂ) (hn : ∀ d ∈ D, nsq (ψ' d) = 1) (out : Qubits n → δ)
(P : ℝ) (hP : ∀ d ∈ D, P ≤ nsq (projOut out d (U.mulVec (ψ' d))))
(good : Qubits n → Prop) [DecidablePred good]
(hgood : ∀ z, ¬ good z → (∑ d ∈ D, ψ' d) z = 0) :
P ≤ nsq (vAcc U D (fun d => ((Real.sqrt D.card)⁻¹ : ℂ) • ψ' d) out) ∧
nsq (offGood good (vAcc U D (fun d => ((Real.sqrt D.card)⁻¹ : ℂ) • ψ' d) out)) ≤
D.card * (1 - P) := by sorry