= Solution
Interpret a <function collision> as two distinct inputs with equal outputs. Without distinctness the request is vacuous, since an input paired with itself always qualifies. Set $m=\lceil N^{1/3}\rceil$ (handling small $N$ by direct queries), choose a known set $A$ of size $m$, and query all its inputs. Store a classical table of their outputs and corresponding inputs. If this table contains a <function collision>, return it immediately.
Otherwise the table contains $m$ distinct outputs. Because $g$ is exactly two-to-one, each $a\in A$ has exactly one partner in $B$, the known complement of $A$. None lies in $A$, and different table outputs have different partners. Thus exactly $m$ inputs in $B$, of size $L=N-m$, satisfy the known-table membership predicate
$$
h(b)=1\quad\Longleftrightarrow\quad g(b)\in\{g(a):a\in A\}.
$$
Build a <marked-state phase oracle> for this predicate by a <compute-phase-uncompute construction>: use $U_g$ on a clean answer <quantum register>, reversibly compare its output against the classical table, apply the conditional minus sign, undo the comparison, and apply $U_g$ again. Since the answer operation is bitwise <exclusive or>, $U_g^{-1}=U_g$. All workspace returns to zero, and each phase query costs two calls to $U_g$.
Perform <known-subset Grover search> in the <span> of the <computational basis> states labelled by $B$, starting in their <uniform superposition state>. Reflection about this known state uses no $U_g$ queries; choosing $A$ as an initial interval makes $B$ a known interval that can also be encoded by its own $L$ labels. Its marked fraction is $m/L$, so the previous <Grover rotation angle> analysis uses $O(\sqrt{L/m})$ phase queries. On measuring $b$, one further $U_g$ query checks the output and retrieves its partner $a$ from the table. The inputs are distinct because the two sets are disjoint.
Consequently the <quantum query complexity> is
$$
\boxed{m+O\!\left(\sqrt{\frac{N-m}{m}}\right)+1=O(N^{1/3}).}
$$
For large $N$, rounding the optimal <Grover search algorithm> iteration count gives success at least $1-m/(N-m)>1/2$. An internal table <function collision> already gives certain success. The balance $m\asymp\sqrt{N/m}$ explains the cube-root choice. This is the <Brassard–Høyer–Tapp collision algorithm>: its table uses $O(m\log N)$ classical bits. The bound counts calls to $U_g$, as requested; it does not charge table lookup and its reversible implementation as constant-time gates, or claim an overall polynomial time in $\log N$.
Back to article page
