Lemma 4.9 — for
OpenQMomentMatch.FirstBound.Supplement.lemma_4_9Setting (§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 .
There is an absolute constant with the following property. Assume (as stated before the lemma, p. 32) , , , and fix with . Let satisfy . Complete with singletons (the frequency vector of Definition 2.1, step 2), let be its number of -blocks (entries equal to ) and its number of -blocks for ; put and . Then for every -query algorithm,
Averaging (29) over random gives Lemma 4.1.
Formalization Note and are real powers of natural numbers; under the hypotheses and , so the denominator is positive. " is an absolute constant" is the existential placed before every other quantity.
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: ρ, b_j counts of blocks of the completion of (w, ℓ) → Multiset.count of ℓ and j in drawsFreq N (appendLast w ℓ); reason: the completion is the base drawsFreq; a j-block is an entry equal to j
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.9, p. 32, under the standing assumptions stated just before it (p. 32):
`N ≥ 8A`, `T ≥ 1`, `T² ≤ N/8`, `2 ≤ ℓ ≤ A`, `T ≤ N^{α_ℓ/(1+α_ℓ)}`. In the completion
`c(w, ℓ)`: `ρ` = number of `ℓ`-blocks, `n_1 = 1 + b_1`, `n_* = min_{1≤j<ℓ} (1 + b_j)`.
`C` is absolute. -/
theorem lemma_4_9 :
∃ 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 ℓ)) →
∀ (W : Type) [Fintype W] [DecidableEq W] (alg : QueryAlg (Fin N) (ZMod N) W T)
(out : (Fin N × ZMod N) × W → Bool) (w : Fin (N / 2 - 1) → Fin (A + 1)),
(∑ i, ((w i : ℕ) : ℝ)) ≤ 3 * (N : ℝ) / 4 →
|newtonW alg out w ℓ| ≤
C ^ (ℓ : ℕ) * (T : ℝ) ^ (1 + alpha ℓ) /
(Real.sqrt (blockCount N w ℓ ℓ : ℝ) * ((1 + blockCount N w ℓ 1 : ℕ) : ℝ) *
((nStar N w ℓ : ℕ) : ℝ) ^ (alpha ℓ - 1 / 2)) := by sorry
end QMomentMatch.FirstBound.Supplement