Inquantum computing, theBrassard–Høyer–Tapp algorithm orBHT algorithm is aquantum algorithm that solves thecollision problem. In this problem, one is givenn and an2-to-1 function and needs to find two inputs thatf maps to the same output. The BHT algorithm only makes queries tof, which matches the lower bound of in theblack box model.[1] The algorithm can be generalized to r-to-1 function with a complexity of.[2]
The algorithm was discovered byGilles Brassard, Peter Høyer, and Alain Tapp in 1997.[3] It usesGrover's algorithm, which was discovered the year before.
Intuitively, the algorithm combines the square root speedup from thebirthday paradox using (classical) randomness with the square root speedup from Grover's (quantum) algorithm.
First,n1/3 inputs tof are selected at random andf 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 byf. Then Grover's algorithm is used to find a new input tof that collides. Since there aren inputs tof andn1/3 of these could form a collision with the already queried values, Grover's algorithm can find a collision with extra queries tof.[3]
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication |
| ||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum processor benchmarks | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Quantum programming | |||||||||
