= Solution
An injective self-map of the finite set $\mathbb Z_N$ is a <bijection>. For sufficiently large $N$, exactly
$$
m=\lfloor N^{1/4}\rfloor+1
$$
outputs satisfy the integer comparison, so there are exactly $m$ good inputs. Prepare the <uniform superposition state> $|\psi\rangle=N^{-1/2}\sum_x|x\rangle$, whose good probability is
$$
p=\frac mN=\Theta(N^{-3/4}).
$$
Use the phase oracle from the previous part and the reflection $2|\psi\rangle\langle\psi|-I$. The <amplitude amplification theorem> requires $O(p^{-1/2})$ iterations; each uses two $U_f$ queries, while the state preparation and its reflection are independent of $f$. With the nearest-integer iteration count from that theorem, the failure probability is at most $p$, tending to zero. Therefore the success probability eventually exceeds $0.9$, with
$$
\boxed{O(N^{3/8})\text{ queries to }U_f.}
$$
This is a bound on <quantum query complexity>; implementation costs of the known gates are not counted as oracle queries.
Back to article page
