Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.6 — second moment-matching bound: ∣Pr⁡Π0,N−Pr⁡Π1,N∣≤CAT2−21−rN1−21−r+Ne−cN/A2|\Pr_{\Pi_{0,N}}-\Pr_{\Pi_{1,N}}|\le C^A\frac{T^{2-2^{1-r}}}{N^{1-2^{1-r}}}+Ne^{-cN/A^2}∣PrΠ0,N​​−PrΠ1,N​​∣≤CAN1−21−rT2−21−r​+Ne−cN/A2, and o(1)o(1)o(1) for T=o(N1/2−1/(2(2r−1)))T=o(N^{1/2-1/(2(2^r-1))})T=o(N1/2−1/(2(2r−1)))

Open
QMomentMatch.FirstBound.Supplement.theorem_2_6

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

lower-boundsmoment-matchingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquantum-query-complexity

Let A≥1A\ge1A≥1 be an integer and X0,X1X_0,X_1X0​,X1​ positive frequency statistics supported on [A][A][A], and let Π0,N,Π1,N\Pi_{0,N},\Pi_{1,N}Π0,N​,Π1,N​ be the distributions on functions f:[N]→[N]f:[N]\to[N]f:[N]→[N] induced by X0,X1X_0,X_1X0​,X1​ through Definition 2.1. Suppose that for an integer r≥2r\ge2r≥2

E[X1]E[X0]=E[X12]E[X02]=⋯=E[X1r−1]E[X0r−1].\frac{\mathbb E[X_1]}{\mathbb E[X_0]}=\frac{\mathbb E[X_1^2]}{\mathbb E[X_0^2]}=\cdots=\frac{\mathbb E[X_1^{r-1}]}{\mathbb E[X_0^{r-1}]}.E[X0​]E[X1​]​=E[X02​]E[X12​]​=⋯=E[X0r−1​]E[X1r−1​]​.
  1. There are absolute constants c,C>0c,C>0c,C>0 such that for all integers N≥CAN\ge CAN≥CA and 0≤T≤cN0\le T\le c\sqrt N0≤T≤cN​, every TTT-query quantum algorithm A\mathcal AA satisfies
∣Pr⁡f∼Π0,N[Af=1]−Pr⁡f∼Π1,N[Af=1]∣≤CA T2−21−rN1−21−r+Nexp⁡(−cNA2).(9)\Big|\Pr_{f\sim\Pi_{0,N}}[\mathcal A^f=1]-\Pr_{f\sim\Pi_{1,N}}[\mathcal A^f=1]\Big|\le C^A\,\frac{T^{2-2^{1-r}}}{N^{1-2^{1-r}}}+N\exp\Big(-\frac{cN}{A^2}\Big).\qquad(9)​f∼Π0,N​Pr​[Af=1]−f∼Π1,N​Pr​[Af=1]​≤CAN1−21−rT2−21−r​+Nexp(−A2cN​).(9)
  1. In particular, for fixed AAA and rrr (and fixed X0,X1X_0,X_1X0​,X1​), the difference is o(1)o(1)o(1) as N→∞N\to\inftyN→∞ whenever T=o(N1/2−1/(2(2r−1)))T=o\big(N^{1/2-1/(2(2^r-1))}\big)T=o(N1/2−1/(2(2r−1))).

Each probability includes the draw of fff and the algorithm's measurement outcomes. For fixed A,rA,rA,r this gives a stronger quantum query lower bound than Theorem 2.5, at the cost of the factor CAC^ACA; it is the paper's second main theorem and yields its applications for fixed support.

Formalization Note The constants c,Cc,Cc,C are chosen before AAA, X0X_0X0​, X1X_1X1​, rrr, NNN, TTT and the algorithm. The exponents are real: T2−21−rT^{2-2^{1-r}}T2−21−r and N1−21−rN^{1-2^{1-r}}N1−21−r use Real.rpow. Part 2 is stated for every sequence of algorithms indexed by nnn, with N=n+1N=n+1N=n+1, TnT_nTn​ queries and workspace Fin(wn)\mathrm{Fin}(w_n)Fin(wn​): if Tn/N1/2−1/(2(2r−1))→0T_n/N^{1/2-1/(2(2^r-1))}\to0Tn​/N1/2−1/(2(2r−1))→0 then the difference tends to 000.

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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me