 Brassard–Høyer–Tapp collision algorithm

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 givesChoosing $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.