Element-distinctness Johnson walk and value access

Let $N\ge 2$, let $\mathcal{V}$ be a finite nonempty value set, and let $f:[N]\to \mathcal{V}$, where $[N]=\{1,\dots ,N\}$. A coherent value oracle is a supplied finite unitary $O_f$ with an explicitly specified injective encoding $\mathrm{enc}:\mathcal{V}\to \{0,1{\}}^b$ for some finite $b$, and action $\mathrm{\mid }i,z⟩\mapsto \mathrm{\mid }i,z\oplus \mathrm{enc}(f(i))⟩$ on valid addresses and target strings, as in Coherent XOR function oracle. Injectivity ensures that stored encodings compare equal exactly when the underlying values do. Oracle-query cost and ordinary gate-occurrence cost are separate coordinates under Finite circuit resource accounting. The function table or name alone supplies no oracle circuit.

For $N\ge 4$ and $2\le r\le \lfloor N\mathrm{/}2\rfloor$, the lazy Johnson walk has state space ${\mathrm{\Omega }}_r=\{S\subseteq [N]:\mathrm{\mid }S\mathrm{\mid }=r\}$ and transitions

$P(S,S)=\frac{1}{2},P(S,S\setminus \{i\}\cup \{j\})=\frac{1}{2r(N-r)}(i\in S,j\mathrm{\notin }S),$

with all other entries zero. Its marked vertices are

${\mathcal{M}}_f:=\{S\in {\mathrm{\Omega }}_r:\mathrm{\exists }i,j\in S,i\mathrm{\ne }j,f(i)=f(j)\}\mathrm{.}$

The stored data at $S$ are the $r$ labeled values $(f(i){)}_{i\in S}$. Preparing the uniform $r$-subset state and loading these values has value-query cost $S_0=r$, with subset preparation gates charged separately. A neighbor update erases the removed value and loads the added value, so its value-query cost is $U_0=2$; the XOR oracle is its own inverse. Checking whether the stored subset is marked uses no further value queries, so $C_0=0$, but comparison gates and memory accesses are charged. After measuring a marked subset, scanning its stored values outputs a colliding pair with no additional value query; the scan's gate/time cost remains separate. For $N\le 3$, use direct pairwise comparison rather than the $r$-subset walk. The lower bound $r\ge 2$ is essential: a one-element subset cannot contain a collision pair.