Classical randomized Simon decision requires square-root-many queries

Consider the finite input distribution that chooses YES or NO with probability $1\mathrm{/}2$. In the YES case choose a uniform permutation of $V_n$. In the NO case choose a uniform nonzero mask $s$, then a uniform injection from the $N\mathrm{/}2$ cosets $\{x,x\oplus s\}$ into the $N$ output labels. Every valid NO function has a unique mask, and each mask has the same number of such injections, so this is uniform over valid NO functions.

It suffices to bound every deterministic query strategy: any randomized strategy has finitely many possible histories and actions up to depth $T$, so its conditional action choices can be represented as a finite distribution over deterministic decision trees. Repeated queries can be removed by caching their earlier answer, so assume every queried address is fresh.

Fix a deterministic strategy and a query index $k\le T$. Since $N\ge 16$, the premise $T\le \sqrt{N}\mathrm{/}8$ implies $k\le N\mathrm{/}2$. Suppose its first $k-1$ distinct query addresses $x_1,\dots ,x_{k-1}$ have produced distinct outputs. Under a NO mask, this transcript is possible exactly when $s\mathrm{\ne }{x}_i\oplus x_j$ for every $i<j<k$. Thus at most $\left(\genfrac{}{}{0px}{}{k-1}{2}\right)$ of the $N-1$ nonzero masks are excluded. For every remaining mask, the queried addresses lie in distinct cosets; the number of injective assignments of output labels to the unqueried cosets is $\frac{(N-k+1)!}{(N\mathrm{/}2)!},$ independent of the mask. Hence, conditioned on this transcript, the mask is uniform among at least $N-1-\left(\genfrac{}{}{0px}{}{k-1}{2}\right)$ candidates.

The next address $x_k$ is determined by the transcript. At most $k-1$ candidate masks, namely $x_k\oplus x_j$ for $j<k$, make its output collide with a previous output. Therefore $\mathrm{Pr}[\text{first collision at query }k\mid \text{no earlier collision}]\le \frac{k-1}{N-1-\left(\genfrac{}{}{0px}{}{k-1}{2}\right)}\mathrm{.}$ If there is no collision, $x_k$ belongs to a new coset whose output label is uniform among the $N-k+1$ unused labels, exactly as the next output of a uniformly random permutation. Couple the two oracle transcripts to use the same unused label until a Simon collision occurs; the adaptive address choices then also agree up to that time.

For $T\le \sqrt{N}\mathrm{/}8$ and $N\ge 16$, each denominator in step 3.1 is at least $N-1-T^2\mathrm{/}2>N\mathrm{/}2$. Summing the conditional first-collision bounds gives ${\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[\text{a collision by query }T]\le {\sum }_{k=2}^T\frac{2(k-1)}{N}=\frac{T(T-1)}{N}\le \frac{1}{64}<\frac{1}{3}\mathrm{.}$ This also bounds the probability that the coupled transcripts differ.

Let $D$ be the deterministic decision bit, with $1$ meaning YES. Under the coupling, its outputs in the two cases differ with probability at most $1\mathrm{/}64$, so ${\mathrm{Pr}}_{\mathrm{Y}\mathrm{E}\mathrm{S}}[D=1]-{\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[D=1]\le \frac{1}{64}\mathrm{.}$ Its average success under the equal mixture is $\frac{1}{2}({\mathrm{Pr}}_{\mathrm{Y}\mathrm{E}\mathrm{S}}[D=1]+{\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[D=0])=\frac{1}{2}(1+{\mathrm{Pr}}_{\mathrm{Y}\mathrm{E}\mathrm{S}}[D=1]-{\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[D=1])\le \frac{1+1\mathrm{/}64}{2}<\frac{2}{3}\mathrm{.}$ By step 1.2 the same bound holds for every randomized algorithm. A worst-case error bound of $1\mathrm{/}3$ would imply average success at least $2\mathrm{/}3$, a contradiction. Therefore at least $\sqrt{N}\mathrm{/}8$ queries are required for all sufficiently large $n$, which is $\mathrm{\Omega }(2^{n\mathrm{/}2})$.