BHT algorithm

In quantum computing, the Brassard-Høyer-Tappar 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 Hoyer, and Alain Tapp in 1997.^[3] 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, n^1/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 n inputs to f and n^1/3 of these would form a collision with the already queried values, Grover's algorithm can find a collision with ${\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}$ extra queries to f.

See also[]

• Element distinctness problem

References[]