From: Michael Nielsen (mnielsen@theory.caltech.edu)
Date: Wed Sep 23 1998 - 09:44:23 MDT
On Wed, 23 Sep 1998 haradon@acsu.buffalo.edu wrote:
> What are the predictions about the speed of a quantum computer?
>
> [ Request for a fast searching algorithm ]
Generally, if you want to search a search space containing n items, a
classical computer takes a number of operations proportional to n. Using
Grover's algorithm, this can be sped up to a time proportional to square
root of n on a quantum computer. Furthermore, it is known that Grover's
algorithm is optimal -- no further speed up is possible for a general
search problem.
Michael Nielsen
http://www.theory.caltech.edu/~mnielsen/
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:36 MST