Content deleted Content added
Bender2k14 (talk | contribs) m →Evaluating NAND trees: Added a reference for the Saks, Wigderson paper |
Bender2k14 (talk | contribs) m →Element distinctness problem: Capitalized the first letter of the title |
||
Line 146:
===Element distinctness problem===
{{main|
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>\Theta(N^{2/3})</math> queries on a quantum computer. The optimal algorithm is by [[Andris Ambainis]].<ref>{{cite journal |last=Ambainis |first=Andris |year=2007 |title=Quantum Walk Algorithm for Element Distinctness |journal=SIAM Journal on Computing |volume=37 |issue=1 |pages=210-239 |publisher=SIAM |doi=10.1137/S0097539705447311 |url=http://link.aip.org/link/?SMJ/37/210/1}}</ref> [[Scott Aaronson]] and Yaoyun Shi first proved a tight lower bound for a large but restricted class of functions.<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> Ambainis extended their work to obtain the lower bound for all functions.<ref>{{cite journal |last=Ambainis |first=Andris |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 |publisher=Theory of Computing |doi=10.4086/toc.2005.v001a003 |url=http://www.theoryofcomputing.org/articles/v001a003}}</ref>
| |||