Re: How fast will a quantum computer be?

Michael Nielsen (
Wed, 23 Sep 1998 08:44:23 -0700 (PDT)

On Wed, 23 Sep 1998 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