Revision as of 03:56, 7 May 2020 edit Citation bot (talk \| contribs) Bots 5,869,929 edits Alter: pages. Add: issue. Formatted dashes. \| You can use this bot yourself. Report bugs here. \| Activated by Philoserf \| Category:Articles with inconsistent citation formats \| via #UCB_Category ← Previous edit		Revision as of 23:34, 8 May 2020 edit undo Marwahaha (talk \| contribs) 34 edits m →Quantum complexity Next edit →
Line 19: ==Quantum complexity== It is also known that [[quantum algorithm]]s can solve this problem faster, in <math>\Theta\left(n^{2/3}\right)</math> queries. The optimal algorithm is by [[Andris Ambainis]].<ref>{{citation \| last1=Ambainis \| first1=Andris \| author1-link=Andris Ambainis \| title=Quantum walk algorithm for element distinctness \| doi = 10.1137/S0097539705447311 \| journal = [[SIAM Journal on Computing]] \| volume = 37 \| issue = 1 \| year = 2007 \| pages=210–239 \| arxiv=quant-ph/0311001 }}</ref> [[Yaoyun Shi]] first proved a tight lower bound when the size of the range is sufficiently large.<ref> {{cite conference \| last1=Shi \| first1=Y.

Element distinctness problem: Difference between revisions