BHT algorithm ============= 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,\ldots,n\}\rightarrow\{1,\ldots,n\} and needs to find two inputs that f maps to the same output. The BHT algorithm only makes O(n^{1/3}) queries to f, which matches the lower bound of \Omega(n^{1/3}) in the black box model. The algorithm can be generalized to r-to-1 function with a complexity of O\left(\left(\frac{n}{r}\right)^{1/3}\right) . The algorithm was discovered by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997. It uses Grover's algorithm, which was discovered the year before. 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,\ldots,n\}\rightarrow\{1,\ldots,n\} and needs to find two inputs that f maps to the same output. The BHT algorithm only makes O(n^{1/3}) queries to f, which matches the lower bound of \Omega(n^{1/3}) in the black box model. The algorithm can be generalized to r-to-1 function with a complexity of O\left(\left(\frac{n}{r}\right)^{1/3}\right) . The algorithm was discovered by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997. It uses Grover's algorithm, which was discovered the year before. ==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, n 1/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 n 1/3 of these could form a collision with the already queried values, Grover's algorithm can find a collision with O\left(\sqrt{\frac{n}{n^{1/3}}}\right) = O(n^{1/3}) extra queries to f. ==See also== Element distinctness problem Grover's algorithm ==References== REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {BHT algorithm}, url = {https://encyclopegia.org/a/bht-algorithm} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - BHT algorithm UR - https://encyclopegia.org/a/bht-algorithm ER - CITE THIS ARTICLE ---------------- Cite this article: BHT algorithm Derived from: https://en.wikipedia.org/w/index.php?oldid=1345499270 Licence: CC BY-SA 4.0 Snapshot: enwiki-001345499270 Permalink: /a/bht-algorithm