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
  1. 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.
  2. 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.
  3. Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998), "Quantum Cryptanalysis of Hash and Claw-Free Functions", in Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.), LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings, Lecture Notes in Computer Science, vol. 1380, Springer, pp. 163–169, arXiv:quant-ph/9705002, doi:10.1007/BFb0054319
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.