Small-query crossing probability for the exact compressed welded-tree oracle
OpenWeldedPath.crossing_probability_boundcompressed-oraclequantum-query-complexitywelded-trees
Put , , and . There are absolute constants such that, for every even , every , every valid properly colored welded-tree instance, and every query algorithm with any finite workspace, the conditions
imply
The probability is that Algorithm 3.10 records a crossing after running against the exact compressed oracle from the empty database. This isolates the accumulated good-space error and crossing exclusion in the proof of Theorem 4.1. Both constants are chosen before all graph and algorithm parameters.
Preamble
import Mathlib import Definitions.Def_WeldedPath_Supplement_pCross
Formal statement
namespace WeldedPath
open QAlgorithms Supplement
theorem crossing_probability_bound :
∃ C₀ : ℝ, 0 < C₀ ∧ ∃ 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,
C₀ * ((q : ℝ) + 1) ≤ (2 : ℝ) ^ (n - l) →
C₀ * (((q : ℝ) + 1) / (2 : ℝ) ^ l +
((n : ℝ) + 1) * ((q : ℝ) + 1) ^ 3 / (2 : ℝ) ^ n) ≤ 1 / 2 →
pCross l G A ≤ C * ((q : ℝ) ^ 2 / (2 : ℝ) ^ l +
(n : ℝ) * (q : ℝ) ^ 3 / (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. Eq. (49), p.27; Eq. (53), p.28; Proposition 4.12, pp.41-42; Section 4.5, p.44, Eq. (75) and the following crossing-probability inequality. The corresponding equations are (56) and (78) in https://arxiv.org/html/2611.05912v1. The bound is the squared accumulated good-space error, with Eq. (49) retained.