From: Hal Finney (hal@rain.org)
Date: Wed Sep 23 1998 - 10:20:59 MDT
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:36 MST