BHT algorithm

In quantum computing, the Brassard–Høyer–Tapp algorithm or BHT algorithm is a quantum algorithm that solves the collision problem. In this problem, one is given n and an 2-to-1 function ${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$ and needs to find two inputs that f maps to the same output. The BHT algorithm only makes ${\displaystyle O(n^{1/3})}$ queries to f, which matches the lower bound of ${\displaystyle \Omega (n^{1/3})}$ in the black box model. The algorithm can be generalized to r-to-1 function with a complexity of ${\displaystyle O\left(\left({\frac {n}{r}}\right)^{1/3}\right)}$.

The algorithm was discovered by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997. It uses Grover's algorithm, which was discovered the year before.