Content deleted Content added
Bender2k14 (talk | contribs) m →Element distinctness problem: Capitalized the first letter of the title |
Bender2k14 (talk | contribs) m →Triangle-finding problem: Capitalized the first letter of the title |
||
Line 151:
===Triangle-finding problem===
{{main|
The triangle-finding problem is the problem of determining whether a given graph contains a triangle (a [[clique (graph theory)|clique]] of size 3). The best-known lower bound for quantum algorithms is Ω(''N''), but the best algorithm known requires O(''N''<sup>1.3</sup>) queries.<ref>{{cite journal |last1=Magniez |first1=Frédéric |last2=Santha |first2=Miklos |last3=Szegedy |first3=Mario |authorlink3=Mario_Szegedy |year=2007 |month=May |title=Quantum Algorithms for the Triangle Problem |journal=SIAM J. Comput. |volume=37 |issue=2 |pages=413-424 |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/050643684 |url=http://portal.acm.org/citation.cfm?id=1328738.1328742 |issn=0097-5397}}</ref><ref>{{cite conference |url=http://doi.acm.org/10.1145/1250790.1250874 |title=Search via quantum walk |last1=Magniez |first1=Frederic |last2=Nayak |first2=Ashwin |last3=Roland |first3=Jeremie |last4=Santha |first4=Miklos |year=2007 |conference=STOC '07 |conferenceurl=http://www2.research.att.com/~dsj/stoc07.html |booktitle=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing |publisher=ACM |pages=575-584 |isbn=978-1-59593-631-8 |doi=http://doi.acm.org/10.1145/1250790.1250874}}</ref>
| |||