Talk:Speedup theorem
Add topicLatest comment: 2 years ago by AmirOnWiki in topic "Unreferenced" template
 | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
Untitled
[edit]I know the quantum result as Grover's algorithm but have not heard of it being called "quadratic speedup theorem". Could you give any sources? Andris 22:28, May 19, 2004 (UTC)
- No sources, it's my own coinage. Does it deserve a mention in this article anyway? Gdr 11:14, 2004 May 20 (UTC)
- No. According to http://www.bell-labs.com/user/feature/archives/lkgrover/ "It will speed up any kind of database search," Grover said. "However the maximum advantage is gained in unsorted databases.". So it seems that it doesn't give quadratic speedup in general. (Actually, I don't see how it gives any speedup at all for an ordered database; it should produce an exponential slowdown, since it still needs time sqrt(N) instead of log(N).) Ben Standeven 00:37, 3 February 2007 (UTC)
"Unreferenced" template
[edit]I think it can be removed, since this article defers the details to the two specific articles. AmirOnWiki (talk) 10:51, 2 September 2023 (UTC)