A constant feasible signing gap forces the near-optimal quantum query bound
ProvedQuantumBipartiteTesting.Bipartiteness.constant_gap_query_lower_boundgraph-testingpolynomial-methodquantum-query-complexity
There are absolute constants and such that the following holds for every . Fix an encoding, an actual finite quantum circuit with 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
then
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 sorrySource
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.