Finite comparison of formal topology moments and feasible pattern containment
ProvedQuantumBipartiteTesting.Bipartiteness.topology_pattern_comparisonfinite-probabilitypolynomial-methodquantum-query-complexity
Fix valid parameters , with , , and . Let be a consistent colored graph pattern on the visible vertices, and suppose
If is sampled by the published feasible hidden-block construction, then its containment probability satisfies
where is the formal topology functional defined by the partition sums (A.2)–(A.4).
This comparison identifies the formal functional through the moments of the observed pattern, rather than defining it to be an overflow-completed graph distribution. The capacity hypothesis ensures that the matching moments for every placement of the pattern are finite probabilities. The result supplies the topology component of the response-monomial comparison in Lemma 3.12.
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction open QuantumBipartiteTesting.Bipartiteness Finset open scoped BigOperators Classical
Formal statement
theorem QuantumBipartiteTesting.Bipartiteness.topology_pattern_comparison {N colors : ℕ} (M l : ℕ) (hv : ValidParameters N M l)
(F : Finset (ColoredEdge N colors)) (hF : Consistent F) (hsmall : 2*F.card ≤ M/l) :
|FeasibleBase N M l (fun G : Finset (ColoredEdge N colors) => if F ⊆ G then (1:ℝ) else 0)-
TopologyMoment F M l| ≤ OverflowProbability N M l := by sorrySource
Kayal–Sen–Szabó, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, §3.2 Definition 3.7, Appendix A.2 equations (A.2)–(A.4), printed pp.30–31, and Appendix A.4 monomial coupling estimate for Lemma 3.12. The explicit finite capacity condition guarantees that each pattern matching moment is a probability.