Majority vote of repeated Hadamard tests: a potential-function lower bound on eigen-label sums
ProvedOPI.LB_majLet be a -qubit register (the phase-gradient register) inside an -qubit system. For a label let be the eigenvector of the increment on , and let be a fixed vector on the qubits outside . For a program , an output event and a real function on labels, say that is a diagonal lower bound for if for all coefficients and every initial classical memory, the (unnormalised) probability that started from produces the event is at least .
The majority stage runs further Hadamard tests (control qubit , ancillas as, exponent , -gates), adding each outcome to a count that starts at , and then continues with if and with otherwise. Let be the amplitude of outcome on ; assume for every . Fix a set of good labels, the correct answer , and with for . Assume are diagonal lower bounds for , with everywhere, on , and . The usual well-formedness conditions are also assumed: the wires are distinct, there are enough ancillas, and vanishes unless the control and the ancillas are . Then for all , a diagonal lower bound for is
where if and if (the number of wrong outcomes seen so far).
In the gradient preparation (stages ), starting with , gives the error factor , which decays exponentially in the number of tests.
import Definitions.Def_TwoFoldOPI_CL_Part03
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
variable {N c' out b : ℕ} {w : Fin b ↪ Fin N} {ψ : (Outside w → Bool) → ℂ}
theorem OPI.LB_maj (c : Fin N) (hc : c ∉ Set.range w) (as : List (Fin N))
(e k : ℕ) (he : e ≤ b) (hlen : 1 + b ≤ as.length + 2) (hnd : ([c] ++ List.ofFn w ++ as).Nodup)
(hψc : ∀ o, o ⟨c, hc⟩ = true → ψ o = 0) (hψ : CleanOn w as ψ) (dst : Fin c')
(event : Option (Fin out → Bool) → Prop) (Nt : ℕ) (P0 P1 : Prog N c' out)
(E : ZMod (2 ^ b) → Prop) [DecidablePred E] (bit : ZMod (2 ^ b) → Bool) (p A B : ℝ)
(hp : 0 ≤ p) (hAB : 0 ≤ A + B)
(hamp : ∀ x : ZMod (2 ^ b), Complex.normSq (tAmp b x.val e k false) +
Complex.normSq (tAmp b x.val e k true) = 1)
(hE : ∀ x, E x → Complex.normSq (tAmp b x.val e k (!bit x)) = p)
(μ : Bool → ZMod (2 ^ b) → ℝ) (h0 : LB w ψ event P0 (μ false)) (h1 : LB w ψ event P1 (μ true))
(hμ : ∀ r x, -B ≤ μ r x) (hμE : ∀ x, E x → A ≤ μ (bit x) x) :
∀ r s, LB w ψ event (majP w c as e k dst Nt P0 P1 r s)
(fun x => if E x then A - (A + B) * potG p Nt r (wrongCnt (bit x) Nt r s) else -B) := by sorry