BHT algorithm

In quantum computing, the Brassard–Høyer–Tapp (BHT) algorithm is a quantum algorithm that solves the collision problem.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 f:{1,…,n}→{1,…,n} and needs to find two inputs that f maps to the same output. The BHT algorithm only makes O(n1/3) queries to f, which matches the lower bound of Ω(n1/3) in the black box model.[1] The algorithm can be generalized to r-to-1 function with a complexity of O((nr)1/3).[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 edit source

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 O(nn1/3)=O(n1/3) extra queries to f.[3]

See also

edit edit source

References

edit edit source
  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
Quantum information scienceGeneral Theorems Quantum
communication Quantum algorithms Quantum
complexity theory
Quantum
processor benchmarks Quantum
computing models Quantum
error correction
Physical
implementations Quantum
programming

Text derived from https://en.wikipedia.org/w/index.php?oldid=1345499270 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001345499270 · captured 1774521079.0 · version history

Cite this page as: encyclopegia.org, “BHT algorithm”, snapshot enwiki-001345499270. https://encyclopegia.org/a/bht-algorithm