= Classical collision query bound for Simon's problem
{title2=$\Theta(2^{n/2})$}
For an unknown nonzero period, a collision $f(x)=f(y)$ reveals the period $x\mathbin\oplus y$. <Birthday problem> sampling finds one using $O(2^{n/2})$ queries with bounded error. A matching lower bound follows by choosing the period and output labels randomly: without a collision, $q$ queries rule out at most $\binom q2$ candidate periods. For $q=o(2^{n/2})$, almost all periods remain consistent with the transcript. The exponential separation is in query complexity, compared with <Simon's algorithm>'s linear quantum query count.
Back to article page
