Revision as of 21:45, 6 December 2010 edit Bender2k14 (talk \| contribs) Extended confirmed users 1,999 edits →Element distinctness problem: "Theta" is not correct here. For example, if the first two elements queries during the "setup phase" collide, we are done. ← Previous edit		Revision as of 01:23, 7 December 2010 edit undo RobinK (talk \| contribs) Extended confirmed users, Pending changes reviewers 3,059 edits Reverted 1 edit by Bender2k14 (talk); "Theta" indicates that the algorithm and lower bound match, not that the algorithm takes exactly that number of queries. (TW) Next edit →
Line 150: {{main\|element distinctness problem}} The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, Ω(''N'') queries are required for a list of size ''N'', since this problem is harder than the search problem which requires Ω(''N'') queries. However, it can be solved in <math>O\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>{{Cite 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===

Quantum algorithm: Difference between revisions