Theorem 2.6 — second moment-matching bound: , and for
OpenQMomentMatch.FirstBound.Supplement.theorem_2_6lower-boundsmoment-matchingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquantum-query-complexity
Let be an integer and positive frequency statistics supported on , and let be the distributions on functions induced by through Definition 2.1. Suppose that for an integer
- There are absolute constants such that for all integers and , every -query quantum algorithm satisfies
- In particular, for fixed and (and fixed ), the difference is as whenever .
Each probability includes the draw of and the algorithm's measurement outcomes. For fixed this gives a stronger quantum query lower bound than Theorem 2.5, at the cost of the factor ; it is the paper's second main theorem and yields its applications for fixed support.
Formalization Note The constants are chosen before , , , , , and the algorithm. The exponents are real: and use Real.rpow. Part 2 is stated for every sequence of algorithms indexed by , with , queries and workspace : if then the difference tends to .
Differences from the source:
- reading: positive frequency statistics X_b supported on [A] → IsPosFreqStat: probability vectors on {0,…,A} with no mass at 0; reason: only the laws enter Definition 2.1 (base convention)
- 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: o(1) as N → ∞ whenever T = o(N^{1/2−1/(2(2^r−1))}) → for all sequences T n, w n, alg n, out n with N = n + 1: Tendsto (T n / N^{1/2−1/(2(2^r−1))}) atTop (𝓝 0) → Tendsto |difference| atTop (𝓝 0); reason: the sequential definition of little-o; a workspace Fin (w n) is any finite workspace up to relabelling
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Query import Definitions.Def_QMomentMatch_FirstBound_Basic import Definitions.Def_QMomentMatch_FirstBound_InducedDist
Formal statement
namespace QMomentMatch.FirstBound.Supplement
open QAlgorithms QMomentMatch.FirstBound Filter Topology
/-- Theorem 2.6, p. 14 (proof §4, pp. 24–33): inequality (9) with absolute constants `c, C > 0`
(chosen before every other quantity), and the "In particular" clause for fixed `A, r`
(and fixed `X₀, X₁`), read over sequences of algorithms with `N = n + 1 → ∞`. -/
theorem theorem_2_6 :
(∃ c C : ℝ, 0 < c ∧ 0 < C ∧
∀ (A : ℕ), 1 ≤ A → ∀ (X₀ X₁ : Fin (A + 1) → ℝ), IsPosFreqStat X₀ → IsPosFreqStat X₁ →
∀ (r : ℕ), 2 ≤ r → PropMoments X₀ X₁ r →
∀ (N T : ℕ) [NeZero N], C * A ≤ N → (T : ℝ) ≤ c * Real.sqrt N →
∀ (W : Type) [Fintype W] [DecidableEq W] (alg : QueryAlg (Fin N) (ZMod N) W T)
(out : (Fin N × ZMod N) × W → Bool),
|probAccept (inducedDist X₀ N) alg out - probAccept (inducedDist X₁ N) alg out| ≤
C ^ A * ((T : ℝ) ^ ((2 : ℝ) - (2 : ℝ) ^ ((1 : ℝ) - r)) /
(N : ℝ) ^ ((1 : ℝ) - (2 : ℝ) ^ ((1 : ℝ) - r))) +
N * Real.exp (-(c * N / A ^ 2))) ∧
(∀ (A : ℕ), 1 ≤ A → ∀ (X₀ X₁ : Fin (A + 1) → ℝ), IsPosFreqStat X₀ → IsPosFreqStat X₁ →
∀ (r : ℕ), 2 ≤ r → PropMoments X₀ X₁ r →
∀ (T w : ℕ → ℕ) (alg : ∀ n, QueryAlg (Fin (n + 1)) (ZMod (n + 1)) (Fin (w n)) (T n))
(out : ∀ n, (Fin (n + 1) × ZMod (n + 1)) × Fin (w n) → Bool),
Tendsto (fun n => (T n : ℝ) /
((n : ℝ) + 1) ^ ((1 : ℝ) / 2 - 1 / (2 * ((2 : ℝ) ^ r - 1)))) atTop (𝓝 0) →
Tendsto (fun n => |probAccept (inducedDist X₀ (n + 1)) (alg n) (out n) -
probAccept (inducedDist X₁ (n + 1)) (alg n) (out n)|) atTop (𝓝 0)) := by sorry
end QMomentMatch.FirstBound.Supplement
Source
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó, STOC 2027 submission #564 (October 2026), Theorem 2.6, p. 14 (proof §4, pp. 24–33)