BHT algorithm
From Wikipedia, the free encyclopedia
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 and needs to find two inputs that f maps to the same output. The BHT algorithm only makes queries to f, which matches the lower bound of 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.