Algorithm 3.9 is a query algorithm with at most 7q+3 queries
ProvedWeldedPath.verifier_realizationFix any welded-tree oracle interface with parameters . Let make queries with finite workspace, and let map its final measurement outcomes to lists of colored labels. There are a finite workspace, an algorithm making exactly queries to the same oracle, and an acceptance event independent of the sampled permutations, such that for every finite sampling set ,
Both expectations use the published finite-average convention, including the empty set. The same and work for all .
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 overhead explicit. It includes the original queries. Graph validity and parity are unnecessary for this operational realization.
import Definitions.Def_WeldedPath_Supplement_pWt
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