Stable canonical coefficients for arbitrary recorded forests
ProvedWeldedPath.forest_coefficient_stabilitycoefficient-stabilityquantum-query-complexitywelded-trees
Let H be any valid abstract forest on k vertices, G a valid welded-tree instance, n≥16 and 2≤l≤n−4. Let B contain V_bd and be disjoint from the weld. Assume
For each valid canonical description of H, form its assignment amplitude before imposing injectivity: sqrt(μ_ref(φ)) when its fixed Wfix data agree and every vertex outside its selected tree components avoids B, and zero otherwise. Let S be the complex span of these amplitudes, including all descriptions, all components and all boundary patterns.
For every f₀ in S there exists f in S such that
The constant is independent of the number and sizes of connected components. This is the stable coefficient representative needed to remove noninjective assignments in the good-space analysis.
Preamble
import Definitions.Def_WeldedPath_Supplement_projGood set_option autoImplicit false
Formal statement
namespace WeldedPath
open Classical Supplement
open scoped BigOperators
theorem forest_coefficient_stability :
∀ n l : ℕ, 16 ≤ n → 2 ≤ l → l ≤ n - 4 →
∀ G : WeldedInstance n, G.IsValid →
∀ H : AbsForest n, H.IsValid →
∀ B : Finset ℕ, Vbd n l ⊆ B → Disjoint B (Vweld n) →
(H.k : ℝ) * (B.card : ℝ) * (4 / (2 : ℝ) ^ n) ≤ 1 / 2 →
2 * (H.k : ℝ) ^ 3 * (96 * ((n : ℝ) + 1) / (2 : ℝ) ^ n) ≤ 1 / 2 →
let amplitude := fun (sel : Finset (Fin H.k)) (φ₀ : Fin H.k → Label n) =>
(WithLp.toLp 2 (fun φ : Fin H.k → Label n =>
if (∀ s ∈ sel, H.Wfix φ s = H.Wfix φ₀ s) ∧
(∀ s ∈ sel, ∀ u, H.graph.Reachable s u → u ∉ H.Ctree φ s → (φ u).val ∉ B)
then (Real.sqrt (H.muRef l G φ) : ℂ) else 0) : Hil (Fin H.k → Label n))
let S := Submodule.span ℂ {f | ∃ sel φ₀,
(Description.mk H sel φ₀).IsValid ∧ f = amplitude sel φ₀}
∀ f₀ : Hil (Fin H.k → Label n), f₀ ∈ S →
∃ f : Hil (Fin H.k → Label n), f ∈ S ∧
(∀ φ, Function.Injective φ → f φ = f₀ φ) ∧
‖f‖ ^ 2 ≤ 2 * ∑ φ, if Function.Injective φ then ‖f₀ φ‖ ^ 2 else 0 := by
sorry
end WeldedPath
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/html/2611.05912v1#S4.SS1, Section 4.1, Lemmas 4.3-4.5. This states the coefficient-stability conclusion for the literal canonical Description span, with explicit constants and arbitrary disconnected forests.