= Brassard–Høyer–Tapp collision algorithm
{c}
{title2=$O(N^{1/3})$}
Query a known set of $m$ inputs and store its output table. If no <function collision> occurs there, each of its $m$ distinct outputs has exactly one partner in the complement, for a two-to-one function. A <compute-phase-uncompute construction> marks those partners using two function queries and reversible table comparison. <Known-subset Grover search> then uses $O(\sqrt{(N-m)/m})$ such phase queries. Including table preparation and a final verification query gives
$$
T(m)=m+O\!\left(\sqrt{\frac{N-m}{m}}\right)+1.
$$
Choosing $m\asymp N^{1/3}$ balances both terms and gives $T(m)=O(N^{1/3})$. The <Grover rotation angle> rounding bound gives success tending to one. This is a query bound; it does not make reversible table lookup free in a gate or physical-memory cost model.
Back to article page
