en>David Eppstein: boldface merged term

2013-09-10T23:30:02Z

boldface merged term

New page

The '''BHT algorithm''' is a [[quantum algorithm]] that solves the [[collision problem]]. In this problem, one is given ''n'' and an ''r''-to-1 function <math>f:\,\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}</math> and needs to find two inputs that ''f'' maps to the same output. The BHT algorithm only makes <math>O(n^{1/3})</math> queries to ''f'', which matches the lower bound of <math>\Omega(n^{1/3})</math> in the [[black box]] model.<ref>
{{cite journal
|last=Ambainis |first=A.
|year=2005
|title=Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
|journal=[[Theory of Computing]]
|volume=1 |issue=1 |pages=37–46
|arxiv=
|bibcode=
|doi=10.4086/toc.2005.v001a003
}}</ref><ref>
{{cite journal
|last1=Kutin |first1=S.
|year=2005
|title=Quantum Lower Bound for the Collision Problem with Small Range
|journal=[[Theory of Computing]]
|volume=1 |issue=1 |pages=29–36
|arxiv=
|bibcode=
|doi=10.4086/toc.2005.v001a002
}}</ref>

The algorithm was discovered by Brassard, Hoyer, and Tapp in 1997.<ref>{{cite arXiv
| last1 = Brassard
| first1 = Gilles
| last2 = Hoyer
| first2 = Peter
| last3 = Tapp
| first3 = Alain
| eprint = quant-ph/9705002
| title = Quantum Algorithm for the Collision Problem
| year = 1997}}</ref> 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, ''n''<sup>1/3</sup> inputs to ''f'' are selected at random and ''f'' and is queried at all of them. If there is a collision among these inputs, then we return the colliding pair of inputs. Otherwise, all the 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 only ''n''<sup>2/3</sup> such inputs to ''f'', Grover's algorithm can find one (if it exists) by making only <math>O(\sqrt{n^{2/3}}) = O(n^{1/3})</math> queries to ''f''.

==See also==
*[[Element distinctness problem]]

==References==
{{reflist}}

[[Category:Quantum algorithms]]

Riffle shuffle permutation - Revision history

en>David Eppstein: boldface merged term