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/