Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
BHT algorithm
open-in-new
<h2 id="algorithm">Algorithm</h2> <p>Intuitively, the algorithm combines the square root speedup from the <a href="/facts/Birthday_attack/he1GAUSM">birthday paradox</a> using (classical) randomness with the square root speedup from Grover's (quantum) algorithm. </p><p>First, <i>n</i>1/3 inputs to <i>f</i> are selected at random and <i>f</i> 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 <i>f</i>. Then Grover's algorithm is used to find a new input to <i>f</i> that collides. Since there are <i>n</i> inputs to <i>f</i> and <i>n</i>1/3 of these could form a collision with the already queried values, Grover's algorithm can find a collision with O ( n n 1 / 3 ) = O ( n 1 / 3 ) {\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})} extra queries to <i>f</i>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Element_distinctness_problem/Mwxm6SRv">Element distinctness problem</a></li> <li><a href="/facts/Grover%2527s_algorithm/SJuxBPpA">Grover's algorithm</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="http://www.theoryofcomputing.org/articles/v001a003/v001a003.pdf" target="_blank">http://www.theoryofcomputing.org/articles/v001a003/v001a003.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="https://doi.org/10.4086%2Ftoc.2005.v001a002" target="_blank">https://doi.org/10.4086%2Ftoc.2005.v001a002</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>