Simon injectivity decision promise with XOR-oracle access

Fix $n\ge 1$ and put $V_n=\{0,1{\}}^n$, with coordinatewise addition $\oplus$ over ${\mathbb{F}}_2$ and cardinality $N=2^n$. For $s,y\in V_n$, define the dot product $s\cdot y={\sum }_{j=0}^{n-1}{s}_j{y}_j(\mathrm{m}\mathrm{o}\mathrm{d}2)$. A table code consists of a unary header $1^{n}0$ followed by the $n$-bit words $f(x)$ in lexicographic order of $x\in V_n$; this identifies function instances with binary strings as in Promise problem, Finite fields and their order, and Big-endian encoding of ordered bit strings.

The YES promise set $Y_n$ consists of table codes of injective maps $f:V_n\to V_n$. The NO promise set $N_n$ consists of codes for which there is a nonzero $s\in V_n$ such that, for every $x,y\in V_n$,

$f(x)=f(y)⟺y=x\text{ or }y=x\oplus s\mathrm{.}$

The sets are disjoint: every NO function has a collision between the distinct inputs $x$ and $x\oplus s$. Its mask is unique, since two different nonzero masks would give a third distinct input in the same fiber. Classical query access returns $f(x)$ at a chosen address. Quantum query access is the coherent XOR oracle $U_f\mathrm{\mid }x,z⟩=\mathrm{\mid }x,z\oplus f(x)⟩$ of Coherent XOR function oracle, which is unitary and involutive by A total Boolean XOR oracle is unitary and involutive. Each call is one query; query charges remain separate from ordinary gate costs by Circuit-family and computation cost model. In the query model the table is not supplied as gate data; the table code fixes the promised function only.