Re: How fast will a quantum computer be?

Hal Finney (hal@rain.org)
Wed, 23 Sep 1998 09:20:59 -0700

A problem like you are describing can be thought of as a search problem. You want to search through a list of candidate values for one which satisfies a certain criterion (in this case, being a CAD specification of a spaceship, etc.).

We have good information about the abilities of quantum computers with this kind of problem. We have a proof of the best speedups possible, and we have an algorithm which gives that much speedup.

Generally, the answer is that the quantum computer takes the square root of the number of operations taken by the classical computer.

In your case, if your classical computer would take 2 to the power of 1 billion possibilities to calculate, the quantum computer would take the square root of that, which means halving the exponent. This is 2 to the power of 500 million possibilities.

This is far too many to be practical. The number of subatomic particles in the entire universe is something like 2 to the 300th. If each one of these was somehow able to function as a separate quantum computer, your problem would still require 2 to the 499,999,700 power calculations.

Hal