Element distinctness problem: Difference between revisions

Revision as of 13:57, 24 May 2014

Revision as of 05:21, 11 February 2015

Line 15:

The same lower bound was later proved for the [[randomized complexity|randomized]] [[algebraic decision tree]] model.<ref>{{citation|doi=10.1007/BF01270387|title=A lower bound for randomized algebraic decision trees|year=1996|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=6|pages=357|last2=Karpinski|first2=Marek|author2-link=Marek Karpinski|last3=Heide|first3=Friedhelm Meyer|last4=Smolensky|first4=Roman|issue=4}}.</ref><ref>{{citation|doi=10.1007/s000370050002|title=Complexity lower bounds for randomized computation trees over zero characteristic fields|year=1999|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=8|pages=316|issue=4}}.</ref>

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> [[ScottYaoyun AaronsonShi]] and Yaoyun Shi first proved a tight lower bound for a large but restricted class of functions.<ref>

{{cite conference

{{Cite journal

| last1=AaronsonShi | first1=SY.

| year=20042002

| last2=Shi | first2=Y.

| year=2004

| title=Quantum lower bounds for the collision and the element distinctness problems

| conference = Proceedings of the 43rd [[Symposium on Foundations of Computer Science]]

| journal=[[Journal of the ACM]]

| volume=51 | issue=4 | pages=595–605513–519

| doi=10.1109/SFCS.2002.1181975

| arxiv=

| bibcode=

| doi=10.1145/1008731.1008735

}}</ref> Ambainis<ref>

{{cite journal

Line 46 ⟶ 43:

|bibcode=

|doi=10.4086/toc.2005.v001a002

}}</ref> independently (and via different proofs) extended theirhis work to obtain the lower bound for all functions.

Several lower bounds in computational complexity are proved by reducing the element distinctness problem to the problem in question, i.e., by demonstrating that the solution of the element uniqueness problem may be quickly found after solving the problem in question.