Quantum algorithm: Difference between revisions

Revision as of 16:43, 17 December 2009

Revision as of 16:44, 17 December 2009

Line 127:

{{main|element distinctness problem}}

The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, &Omega;(''N'') queries are required for a list of size ''N'', since this problem is harder than the search problem which requires &Omega;(''N'') queries. However, it can be solved in <math>\Theta(N^{2/3})</math> queries on a quantum computer. The optimal algorithm is by [[Andris Ambainis]],<ref>A. Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (2007), no. 1, 210–239, quant-ph/0311001, preliminary version in FOCS 2004.</ref> and the lower bound is due to [[Scott Aaronson]] and Yaoyun Shi.<ref>{{CitationCite journal | last1=Aaronson | first1=S. | last2=Shi | first2=Y. | title=Quantum lower bounds for the collision and the element distinctness problems | publisher=Association for Computing Machinery, Inc, One Astor Plaza, 1515 Broadway, New York, NY, 10036-5701, USA, | year=2004 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=51 | issue=4 | pages=595–605 | doi=10.1145/1008731.1008735}}</ref>

===Triangle-finding problem===