Talk:Speedup theorem
From Wikipedia, the free encyclopedia
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)
