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 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 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, n1/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 n1/3 of these would form a collision with the already queried values, Grover's algorithm can find a collision with extra queries to f.
See also[]
References[]
- ^ Ambainis, A. (2005). "Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range" (PDF). Theory of Computing. 1 (1): 37–46. doi:10.4086/toc.2005.v001a003.
- ^ Kutin, S. (2005). "Quantum Lower Bound for the Collision Problem with Small Range". Theory of Computing. 1 (1): 29–36. doi:10.4086/toc.2005.v001a002.
- ^ Brassard, Gilles; Hoyer, Peter; Tapp, Alain (1997). "Quantum Cryptanalysis of Hash and Claw-Free Functions". Lecture Notes in Computer Science: 163–169. arXiv:quant-ph/9705002. doi:10.1007/BFb0054319.
- Quantum algorithms