Lemma 4.1 — averaged bound and
OpenQMomentMatch.FirstBound.Supplement.lemma_4_1Setting (§4.1, p. 24). Fix integers , and and a quantum algorithm making standard queries to , with acceptance probability . Let , , and for let , where is the frequency vector of step 2 of Definition 2.1. For put and let be its Newton coefficients (20). Let . Let .
There is an absolute constant with the following property. Assume , and , and let satisfy . Let be a mean-one distribution on (a probability distribution with ) with for every . Then for every -query algorithm,
and
The proof of Theorem 2.6 applies this along linear paths of distributions to bound the residual term of the comparison Lemma 3.8.
Formalization Note The expectation and probability are finite sums over weighted by (base prodExp); and are real powers. The probability bound does not involve the algorithm and is stated outside the quantifier over algorithms.
Differences from the source:
- encoding: a T-query quantum algorithm on f : [N] → [N] → QueryAlg (Fin N) (ZMod N) W T with any finite workspace W, any unitaries and start state, any output map out, standard oracle xorOracle f; reason: the base mission's algorithm model (theorem_2_5); [N] is Fin N for positions and ZMod N for labels
- encoding: S = {0} ∪ [A], w ∈ S^{m−1}, (w, s), m = ⌊N/2⌋ → Fin (A + 1), w : Fin (N / 2 - 1) → Fin (A + 1), appendLast w s, N / 2; reason: same conventions as the base definitions; s is placed in the last coordinate as on p. 18
- encoding: C is an absolute constant → ∃ C : ℝ, 0 < C placed before N, A, T, ℓ, the algorithm and w; reason: absolute means independent of every other quantity; requiring C > 0 loses nothing since enlarging to 1 + |C| preserves the bound
- encoding: an integer ℓ with 2 ≤ ℓ ≤ A → ℓ : Fin (A + 1) with 2 ≤ (ℓ : ℕ); reason: Fin (A + 1) carries ℓ ≤ A; ℓ is also a value of S as needed for the completion (w, ℓ)
- encoding: π a mean-one distribution on S → IsProbVec π ∧ moment π 1 = 1; reason: base definitions of a law on S and its first moment
import Mathlib import Definitions.Def_QAlgorithms_Defs_Query import Definitions.Def_QMomentMatch_FirstBound_Basic import Definitions.Def_QMomentMatch_FirstBound_InducedDist import Definitions.Def_QMomentMatch_FirstBound_Supplement_NewtonCoeff
namespace QMomentMatch.FirstBound.Supplement
open QAlgorithms QMomentMatch.FirstBound
/-- Lemma 4.1, p. 24 (proof p. 32), in the setting of §4.1: `m = ⌊N/2⌋`,
`G = {w ∈ S^{m−1} : ∑ w_i ≤ 3N/4}`, `w ∼ π^{⊗(m−1)}`. `C` is absolute. -/
theorem lemma_4_1 :
∃ C : ℝ, 0 < C ∧
∀ (N A T : ℕ) [NeZero N] (ℓ : Fin (A + 1)),
8 * A ≤ N → 1 ≤ T → (T : ℝ) ^ 2 ≤ (N : ℝ) / 8 → 2 ≤ (ℓ : ℕ) →
(T : ℝ) ≤ (N : ℝ) ^ (alpha ℓ / (1 + alpha ℓ)) →
∀ (π : Fin (A + 1) → ℝ), IsProbVec π → moment π 1 = 1 →
∀ a : ℝ, 0 < a → (∀ s, a ≤ π s) →
(∀ (W : Type) [Fintype W] [DecidableEq W] (alg : QueryAlg (Fin N) (ZMod N) W T)
(out : (Fin N × ZMod N) × W → Bool),
prodExp π (fun w : Fin (N / 2 - 1) → Fin (A + 1) =>
goodInd N w * |newtonW alg out w ℓ|) ≤
C ^ (ℓ : ℕ) * (T : ℝ) ^ (1 + alpha ℓ) / N *
(((N / 2 : ℕ) : ℝ) * a) ^ (-alpha ℓ)) ∧
prodExp π (fun w : Fin (N / 2 - 1) → Fin (A + 1) => 1 - goodInd N w) ≤
Real.exp (-((N : ℝ) / (4 * (A : ℝ) ^ 2))) := by sorry
end QMomentMatch.FirstBound.Supplement