The BHT algorithm is a quantum algorithm that solves the collision problem. In this problem, one is given n and an r-to-1 function
The algorithm was discovered by Brassard, Hoyer, and Tapp in 1997. It uses Grover's algorithm, which was discovered in the previous year.
Algorithm
Intuitively, the algorithm combines the square root speedup from the birthday paradox using (classical) randomness with the square root speedup from Grover's (quantum) algorithm.
First, n1/3 inputs to f are selected at random and f is queried at all of them. If there is a collision among these inputs, then we return the colliding pair of inputs. Otherwise, all these inputs map to distinct values by f. Then Grover's algorithm is used to find a new input to f that collides. Since there are only n2/3 such inputs to f, Grover's algorithm can find one (if it exists) by making only