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 r-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.^[1][2]

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