Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Algorithm 3.9 is a query algorithm with at most 7q+3 queries

Proved
WeldedPath.verifier_realization

by dmilosch · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

quantum-algorithmsquantum-query-complexitywelded-trees

Fix any welded-tree oracle interface with parameters n,l,Gn,l,Gn,l,G. Let AAA make q≥1q\ge1q≥1 queries with finite workspace, and let ooo map its final measurement outcomes to lists of colored labels. There are a finite workspace, an algorithm BBB making exactly 7q+37q+37q+3 queries to the same oracle, and an acceptance event EEE independent of the sampled permutations, such that for every finite sampling set SSS,

Eσ∈SPr⁡[BOσ∈E]=Eσ∈SPr⁡[Accepts⁡3.9(σ,q,o(AOσ))].\mathbb E_{\sigma\in S}\Pr[B^{O_\sigma}\in E] =\mathbb E_{\sigma\in S}\Pr[\operatorname{Accepts}_{3.9}(\sigma,q,o(A^{O_\sigma}))].Eσ∈S​Pr[BOσ​∈E]=Eσ∈S​Pr[Accepts3.9​(σ,q,o(AOσ​))].

Both expectations use the published finite-average convention, including the empty set. The same BBB and EEE work for all SSS.

This realizes the source's standard-oracle verification procedure in the unitary query-algorithm model, so distribution-comparison lemmas for oracle-independent accepting events apply.

Formalization Note. The exact query count makes the source's O(q)O(q)O(q) overhead explicit. It includes the original qqq queries. Graph validity and parity are unnecessary for this operational realization.

Preamble
import Definitions.Def_WeldedPath_Supplement_pWt
Formal statement
namespace WeldedPath

open QAlgorithms Supplement

/-- Algorithm 3.9 implemented as one query algorithm with a fixed acceptance event.
The bound `7*q+3` is derived by counting its verification queries for `q ≥ 1`:
at most `2*q+4` on the short-output branch and `6*q+3` on the long-output branch,
in addition to the original `q` queries. No validity assumption on `G` is needed
for this operational statement. -/
theorem verifier_realization (n l : ℕ) (G : WeldedInstance n)
    (W : Type) [Fintype W] [DecidableEq W] (q : ℕ) (hq : 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))) :
    ∃ (W' : Type) (instF : Fintype W') (instD : DecidableEq W'),
      letI : Fintype W' := instF
      letI : DecidableEq W' := instD
      ∃ (B : QueryAlg (Qubits (2 * n + 1) × Fin 3) (Qubits (2 * n + 1)) W' (7 * q + 3))
        (acc : ((Qubits (2 * n + 1) × Fin 3) × Qubits (2 * n + 1)) × W' → Prop),
        ∀ S : Finset (Equiv.Perm (Label n) × Equiv.Perm G.edges),
          G.probOver l S B (fun _ => acc) =
            G.probOver l S A (fun σ z => Accepts39 l G σ q (out z)) := 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, Algorithm 3.9, p.24, steps 2-4; Section 4.5, p.44, the verifier A_ver preceding the probability comparison. The explicit bound 7q+3 and the unitary realization are derived bookkeeping for the stated O(q)-query verification procedure, not a quoted theorem of the source.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me