Theorem 4.1 — Quantum expansion testing needs Ω(N^(1/3)/(log N)^(4/3)) queries
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.theorem_4_1For every fixed degree bound , there is such that for every there is with the following property. For every fixed , there are and such that, for every integer , every two-sided quantum tester which accepts every -vertex-expander and rejects every graph -far from -vertex-expansion, each with probability at least , satisfies
Correctness ranges over all simple graphs of maximum degree at most and every packed adjacency ordering. Arbitrary finite complex workspace and injective binary response encodings are included. Every sufficiently large final size is covered, including nonproducts of intermediate size and color count; is included. This is the paper's independent companion theorem, not a prerequisite for the published bipartiteness goal.
Differences from the source:
- encoding: vertices [n] and asymptotic notation → Fin n, natural logarithms and explicit uniform constants/thresholds; reason: bijective vertex labeling and logarithm-base changes preserve all source instances
- reading: Remark 2.6 prints alpha at most alpha-prime, whereas both formal Theorem 4.1 statements print alpha-prime at most alpha → alpha-prime at most alpha, including equality, with the remarks' small-fixed-parameter convention; reason: pp.21 and 27 agree with the proof; the positive YES constant is chosen above the final threshold
- encoding: bounded fixed degree and sufficiently small fixed parameters → d at least 4, alpha0 before alpha,alpha-prime, epsilon0 before epsilon, and C,N0 before N and tester; reason: the degree-four hard instances work for all fixed larger d with normalization epsilondN; this expands the standing conventions without assuming hardness
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
/-- The formal theorem's α' ≤ α ordering is used, with the small-parameter
convention of Remarks 2.4 and 2.6. The two printed formal statements agree. -/
theorem theorem_4_1 (d : ℕ) (hd : 4 ≤ d) :
∃ α₀ : ℝ, 0 < α₀ ∧ α₀ < 1 ∧ ∀ α α' : ℝ,
0 < α' → α' ≤ α → α ≤ α₀ →
∃ ε₀ : ℝ, 0 < ε₀ ∧ ε₀ < 1 ∧ ∀ ε : ℝ, 0 < ε → ε ≤ ε₀ →
∃ C : ℝ, 0 < C ∧ ∃ N₀ : ℕ, 2 ≤ N₀ ∧ ∀ N ≥ N₀,
∀ k w q : ℕ, ∀ E : Encoding (Fin N) k,
∀ A : Algorithm (Address N d) k w q,
∀ out : (Address N d × Bits k) × Fin w → Bool,
ExpansionTester ε α α' E A out → C * ExpansionScale N ≤ (q : ℝ) := by sorry
end QuantumBipartiteTesting.Bipartiteness.Supplement