Editing Quantum algorithm (section)

===Element distinctness problem===
{{main|Element distinctness problem}}

The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, <math>\Omega(N)</math> queries are required for a list of size <math>N</math>; however, it can be solved in <math>\Theta(N^{2/3})</math> queries on a quantum computer. The optimal algorithm was put forth by [[Andris Ambainis]],<ref>
{{cite journal
 |last=Ambainis |first=A.
 |year=2007
 |title=Quantum Walk Algorithm for Element Distinctness
 |journal=[[SIAM Journal on Computing]]
 |volume=37 |issue=1 |pages=210–239
 |arxiv= quant-ph/0311001
 |doi=10.1137/S0097539705447311
|s2cid=6581885
 }}</ref> and [[Yaoyun Shi]] first proved a tight lower bound when the size of the range is sufficiently large.<ref>
{{cite conference
 | last1=Shi | first1=Y.
 | title=The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
 | year=2002
 | chapter=Quantum lower bounds for the collision and the element distinctness problems
 | conference = Proceedings of the 43rd [[Symposium on Foundations of Computer Science]]
 | pages=513–519
 | arxiv = quant-ph/0112086
 | doi=10.1109/SFCS.2002.1181975| isbn=0-7695-1822-2
 }}</ref> Ambainis<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
 |doi=10.4086/toc.2005.v001a003
|doi-access=free
 }}</ref> and Kutin<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
 |doi=10.4086/toc.2005.v001a002
|doi-access=free
 }}</ref> independently (and via different proofs) extended that work to obtain the lower bound for all functions.