Inverse-label compression preserves goodness with explicit leakage bound
ProvedWeldedPath.Supplement.inverse_label_goodnesscompressed-oraclesquantum-query-complexitywelded-trees
Let M=2^(2n), N=2^n, and let G be a valid welded-tree instance with n≥16 and 2≤l≤n−4. Let B contain the canonical boundary and avoid the weld vertices. Suppose t≤M and
For the literal canonical inverse-label compression operator and canonical database good-space projectors,
The query register is coherent and unrestricted. The conclusion is an operator-norm estimate on the entire good subspace, including superpositions across different forest descriptions.
Preamble
import Definitions.Def_WeldedPath_Supplement_projGood set_option autoImplicit false
Formal statement
namespace WeldedPath.Supplement
theorem inverse_label_goodness {n l : ℕ} (G : WeldedInstance n)
(hG : G.IsValid) (hn : 16 ≤ n) (hl : 2 ≤ l) (hln : l ≤ n - 4)
(B : Finset ℕ) (hB : Vbd n l ⊆ B) (hBw : Disjoint B (Vweld n))
(t : ℕ) (htM : t ≤ labelBound n)
(hsurvive : (2 * (t : ℝ)) * (B.card : ℝ) * (4 / (2 : ℝ) ^ n) ≤ 1 / 2)
(hcollision : 2 * (2 * (t : ℝ)) ^ 3 * (96 * ((n : ℝ) + 1) / (2 : ℝ) ^ n) ≤ 1 / 2) :
‖((1 : Hil (QReg n × Db l G) →L[ℂ] Hil (QReg n × Db l G)) -
projGoodB l G B (t+1)).comp ((pCinvLab l G).comp (projGoodB l G B t))‖ ≤
Real.sqrt (16 * (t : ℝ) / ((labelBound n - t + 1 : ℕ) : ℝ)) := by
sorry
end WeldedPath.Supplement
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/html/2611.05912v1, Lemma4.7; explicit constants and coefficient-stability hypotheses.