Loop-erased path verification transfers success to the product distribution
ProvedWeldedPath.verifier_comparisoncompressed-oraclequantum-query-complexitywelded-trees
Let be even, , and let be a valid welded-tree instance with a proper three-coloring. There is an absolute constant such that every query algorithm , with any finite workspace and output map to lists of colored labels, admits another output map satisfying
Here is the acceptance probability of Algorithm 3.9 under the product distribution. The new output map may erase loops using only the output labels, without further queries or knowledge of the sampled oracle. Its existential quantifier accommodates the walk-based success predicate while the verifier requires distinct path labels. This statement isolates the verifier and distribution-comparison part of the proof of Theorem 4.1.
Preamble
import Mathlib import Definitions.Def_WeldedPath_Supplement_pWt
Formal statement
namespace WeldedPath
open QAlgorithms Supplement
theorem verifier_comparison :
∃ C : ℝ, 0 < C ∧
∀ n l : ℕ, Even n → 16 ≤ n → 2 ≤ l → l ≤ n - 4 →
∀ G : WeldedInstance n, G.IsValid →
∀ (W : Type) [Fintype W] [DecidableEq W] (q : ℕ), 1 ≤ q →
∀ (A : QueryAlg (Qubits (2 * n + 1) × Fin 3) (Qubits (2 * n + 1)) W q)
(out : ((Qubits (2 * n + 1) × Fin 3) × Qubits (2 * n + 1)) × W →
List (Fin 3 × Qubits (2 * n + 1))),
∃ out' : ((Qubits (2 * n + 1) × Fin 3) × Qubits (2 * n + 1)) × W →
List (Fin 3 × Qubits (2 * n + 1)),
G.successProb l A out ≤
C * (pWt l G A out' + (n : ℝ) * (q : ℝ) ^ 2 / (2 : ℝ) ^ n) := by sorry
end WeldedPath
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/pdf/2611.05912v1. Section 3.3, p.23 (loop removal), Algorithm 3.9, p.24; Lemma 4.13, pp.42-43; Section 4.5, p.44, first two inequalities after Eq. (78). The accumulated-error equation is numbered (75) in the PDF and (78) in https://arxiv.org/html/2611.05912v1. The loop-erased output is explicit because the target success predicate counts walks.