Balancedness testing promises force a constant feasible center gap
ProvedQuantumBipartiteTesting.Bipartiteness.colored_tester_center_gapfinite-probabilitygraph-testingquantum-query-complexity
There is an absolute with the following property. Let and . Suppose an actual quantum circuit on the three-color signed adjacency oracle accepts every balanced consistent colored graph with probability at least , and accepts every consistent graph with frustration at least with probability at most . Then its feasible distributional signing gap satisfies
All encodings, finite workspaces, query counts and computational-basis output events are allowed. The threshold is chosen before all circuit data. This is the concrete testing-promise interface for the analytic query lower bound.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.colored_tester_center_gap : ∃ N₀ : ℕ, 120 ≤ N₀ ∧ ∀ N ≥ N₀, ∀ ε : ℝ, 0 < ε → ε ≤ 1/300 →
∀ 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,
(∀ F : Finset (ColoredEdge N), Consistent F → ∀ b : ColoredEdge N → Bool,
(Balanced F b → 2/3 ≤ Accept E A out (LiftOracle (SignedResponse F b))) ∧
(ε*N*3 ≤ (Frustration F b:ℝ) → Accept E A out (LiftOracle (SignedResponse F b)) ≤ 1/3)) →
(1/4:ℝ) ≤ FeasibleGap E A out (Center N) 1 := by sorrySource
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, §3.1 center hard distribution and deterministic edge count (also described in the introduction), Lemma 3.3 and Remark 3.4, printed pp.12–14; used in §3.5 Theorem 3.2. Explicit epsilon<=1/300 and gap1/4 retain the given two-sided error without amplification.