BHT algorithm

In <a href="/facts/Quantum_computing/nbbcgmvq">quantum computing</a>, the Brassard–Høyer–Tapp algorithm or BHT algorithm is a <a href="/facts/Quantum_algorithm/ceJaJ6Eq">quantum algorithm</a> that solves the <a href="/facts/Collision_problem/Hr63dS3u">collision problem</a>. In this problem, one is given n and an r-to-1 function 
 
 
 
 f
 :
 
 {
 1
 ,
 …
 ,
 n
 }
 →
 {
 1
 ,
 …
 ,
 n
 }
 
 
 {\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 
 
 
 
 O
 (
 
 n
 
 1
 
 /
 
 3
 
 
 )
 
 
 {\displaystyle O(n^{1/3})}
 
 queries to f, which matches the lower bound of 
 
 
 
 Ω
 (
 
 n
 
 1
 
 /
 
 3
 
 
 )
 
 
 {\displaystyle \Omega (n^{1/3})}
 
 in the <a href="/facts/Black_box/hJeAGnIz">black box</a> model.
The algorithm was discovered by <a href="/facts/Gilles_Brassard/sBxLIE3P">Gilles Brassard</a>, Peter Høyer, and Alain Tapp in 1997. It uses <a href="/facts/Grover%2527s_algorithm/SJuxBPpA">Grover's algorithm</a>, which was discovered the year before.

BHT algorithm open-in-new

BHT algorithm