Quire

BHT algorithm

From Quire, the open reference·Quantum algorithm·1 min read

In quantum computing, the Brassard–Høyer–Tapp (BHT) algorithm is a quantum algorithm that solves the collision problem. In this problem, one is given n and an 2-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] The algorithm can be generalized to r-to-1 function with a complexity of {\displaystyle O\left(\left({\frac {n}{r\right)^{1/3}\right)}.[2]

The algorithm was discovered by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997.[3] It uses Grover's algorithm, which was discovered the year before.

Algorithm#edit

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 could 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.[3]

See also#edit

References#edit

  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. ^ a b Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998), "Quantum Algorithm for the Collision Problem", 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, S2CID 3116149
Categories Quantum algorithms

This article is mirrored from “BHT algorithm” on English Wikipedia, revision 1345499270, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1345499270 · just now