Self-adjoint contraction of exact compressed permutation queries and coherent controls
ProvedWeldedPath.exact_query_contractioncompressed-oraclesoperator-theorypartial-isometriesquantum-query-complexity
Let be nonnegative integers. For an arbitrary answer encoding , a queried point , and either the forward or inverse direction, let be the canonical exact compressed permutation query. Then
The result is uniform in the encoding; injectivity of is not required. For any finite control set , the encoding, queried point, and direction may depend on . The coherently controlled operator
also satisfies and .
This establishes the self-adjointness and contraction clauses of Lemma 2.8 for the canonical exact compressed-oracle construction, including the encoded answers used by the welded-tree oracle. The separate intertwining, database-size transition, and exact-versus-ordinary comparison clauses are outside this statement.
Preamble
import Definitions.Def_WeldedPath_Supplement_exactCpWT set_option autoImplicit false
Formal statement
namespace WeldedPath
open Classical Supplement QAlgorithms
universe u
theorem exact_query_contraction :
∀ s d : ℕ,
(∀ (enc : Fin s → Qubits d) (x : Fin s) (inv : Bool),
ContinuousLinearMap.adjoint (exactCpOE enc x inv) = exactCpOE enc x inv ∧
‖exactCpOE enc x inv‖ ≤ 1) ∧
(∀ (C : Type u) [Fintype C] [DecidableEq C]
(enc : C → Fin s → Qubits d) (x : C → Fin s) (inv : C → Bool),
ContinuousLinearMap.adjoint (controlled (fun c => exactCpOE (enc c) (x c) (inv c))) =
controlled (fun c => exactCpOE (enc c) (x c) (inv c)) ∧
‖controlled (fun c => exactCpOE (enc c) (x c) (inv c))‖ ≤ 1) := by
sorry
end WeldedPath
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/html/2611.05912v1, Lemma 2.8 and equations (10)-(14), with the encoded-answer convention of the canonical Supplement.exactCpOE definition and coherent-control convention of Section 2.1.