Lemma 4.8 — singleton case: for
OpenQMomentMatch.FirstBound.Supplement.lemma_4_8moment-matchingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-methodquantum-query-complexity
Setting (§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. Suppose , and , and let satisfy . Then for every -query algorithm and every ,
This handles the singleton branch in the proof of Lemma 4.9, where every sampled multiplicity is or .
Formalization Note " is an absolute constant" is the existential placed before , the algorithm and .
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, ℓ)
Preamble
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
Formal statement
namespace QMomentMatch.FirstBound.Supplement
open QAlgorithms QMomentMatch.FirstBound
/-- Lemma 4.8, pp. 31–32 (singleton case), in the setting of §4.1 (p. 24): a `T`-query algorithm
on `f : [N] → [N]`, `m = ⌊N/2⌋`, `S = {0} ∪ [A]`, `d_ℓ(w)` of eq. (20). `C` is absolute: it is
chosen before every other quantity. -/
theorem lemma_4_8 :
∃ 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 : ℕ) ≤ 1) →
|newtonW alg out w ℓ| ≤ C ^ (ℓ : ℕ) * (T : ℝ) ^ (1 + alpha ℓ) / N := by sorry
end QMomentMatch.FirstBound.Supplement
Source
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó, STOC 2027 submission #564 (October 2026), Lemma 4.8, pp. 31–32 (setting §4.1, p. 24)