Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A constant feasible signing gap forces the near-optimal quantum query bound

Proved
QuantumBipartiteTesting.Bipartiteness.constant_gap_query_lower_bound

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-testingpolynomial-methodquantum-query-complexity

There are absolute constants c>0c>0c>0 and N0≥2N_0\ge2N0​≥2 such that the following holds for every N≥N0N\ge N_0N≥N0​. Fix an encoding, an actual finite quantum circuit with qqq queries to the three-color signed adjacency oracle, and a computational-basis output event. If its feasible YES-minus-NO acceptance gap at the center distribution satisfies

Δfeas(M0,1)≥14,\Delta_{\mathrm{feas}}(M_0,1)\ge\frac14,Δfeas​(M0​,1)≥41​,

then

q≥cN1/3log⁡N.q\ge c\frac{N^{1/3}}{\log N}.q≥clogNN1/3​.

The constants precede all input sizes and circuit data. This is the analytic lower-bound step: it converts a constant distinguishing gap on the concrete hidden-block distributions into an operational quantum query lower bound, with arbitrary finite workspace and both signing laws retained.

Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
open QuantumBipartiteTesting.Bipartiteness
open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.constant_gap_query_lower_bound : ∃ c : ℝ, 0 < c ∧ ∃ N₀ : ℕ, 2 ≤ N₀ ∧ ∀ N ≥ N₀, ∀ k w q : ℕ,
    ∀ E : Encoding (Fin N × Bool) k, ∀ A : Algorithm (Address N 3) k w q,
    ∀ out : (Address N 3 × Bits k) × Fin w → Bool,
      (1/4:ℝ) ≤ FeasibleGap E A out (Center N) 1 → c*LowerBoundScale N ≤ (q:ℝ) := by sorry
Source
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, §3.5 proof of Theorem 3.2, equations (22)–(28), printed pp.19–20, using Proposition 3.13 and Lemma 3.15. This variant retains the polynomial factor of l and uses the zero-anchored grid estimate, so a center gap of 1/4 suffices without error amplification.

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