Coupling single-cycle and product welded-tree distributions
ProvedWeldedPath.single_cycle_couplingThere is an absolute constant with the following property. Let be even, , and let be a valid properly three-colored welded-tree instance whose single-cycle support is nonempty. Put . There is a nonnegative joint weight on pairs of label-and-edge permutations with uniform marginals on and . For every fixed first sample and every query input ,
All sums range over the full finite permutation space. Zero marginal mass and nonnegativity force zero joint mass outside . The disagreement bound is conditional on each entire single-cycle sample, rather than merely averaged over that distribution. The statement concerns only the graph distributions and their classical oracle answers; it has no algorithm, workspace, or query-count parameter. It is the coupling input to the quantum hybrid argument.
import Definitions.Def_WeldedPath_successProb
namespace WeldedPath
open QAlgorithms
open scoped BigOperators
/-- The finite coupling constructed in the proof of Lemma 4.13, before the quantum
hybrid argument (Carolan et al., arXiv:2611.05912v1, Section 4.4, equations (76)--(77)
and the conditional oracle-disagreement display following (77)).
The first marginal is uniform on `singSupport`; the second is uniform on
`prodSupport`. For EACH fixed single-cycle sample and EACH query input, the
conditional probability of different oracle answers is at most `K*n/2^n`.
The joint weights are extended by zero off the product of the two supports.
There are no quantum-algorithm parameters in this combinatorial statement. -/
theorem single_cycle_coupling :
∃ K : ℝ, 0 < K ∧
∀ n l : ℕ, Even n → 2 ≤ l → l ≤ n - 4 →
∀ G : WeldedInstance n, G.IsValid → (G.singSupport l).Nonempty →
∃ w : (Equiv.Perm (Label n) × Equiv.Perm G.edges) →
(Equiv.Perm (Label n) × Equiv.Perm G.edges) → ℝ,
(∀ σh σg, 0 ≤ w σh σg) ∧
(∀ σh, (∑ σg, w σh σg) =
if σh ∈ G.singSupport l then 1 / ((G.singSupport l).card : ℝ) else 0) ∧
(∀ σg, (∑ σh, w σh σg) =
if σg ∈ G.prodSupport l then 1 / ((G.prodSupport l).card : ℝ) else 0) ∧
(∀ σh (x : Qubits (2 * n + 1) × Fin 3),
(∑ σg, if G.oracleFn l σg x ≠ G.oracleFn l σh x then w σh σg else 0) ≤
(K * (n : ℝ) / (2 : ℝ) ^ n) *
(if σh ∈ G.singSupport l then 1 / ((G.singSupport l).card : ℝ) else 0)) := by
sorry
end WeldedPath