On Tue, 24 Mar 1998 Hal Finney <hal@rain.org> Wrote:
>I want to make a claim on the FX site (the current name for the game
>based on Robin Hanson's Idea Futures) about quantum computing.[...]
>Another approach would be to require successfully factoring a 50 bit
>number using Shor's algorithm or some improvement.
I don't think factoring would be the best test of a Quantum Computer for 3
reasons:
1) Factoring is one of the most demanding tasks you could ask a quantum
computer to do.
2) As you point out, with a 50 bit number cheating is possible with a
conventional computer.
3) It's dull, even if you're able to do it the world will not be changed much.
Rather than factoring a 50 bit number try simulating the behavior of 50
objects, like the 50 electrons in a tin atom. That would change the world big
time, yet surprisingly it would be much easier to get a quantum computer to
do that than factor numbers. There is no way a conventional computer could
perform such a simulation, that's why Chemists must still do experiments.
To simulate the behavior of N electrons, in a conventional computer you would
need memory space and computation time proportional to 2^2N. To figure out
from theory alone what's going on with a tin atom you would need to perform
about 10^30 operations.
Seth Lloyd found a way to perform the same simulation using just N qubits and
the number of operations the quantum machine must do is proportional to N,
not 2^2N as on a conventional computer. In addition, the time required to do
the simulation over time t is proportional to t, in other words it can do it
in real time, like an Analog computer. Lloyd's simulation method is far more
forgiving and less sensitive to errors than Shor's factoring algorithm, and
astronomically more useful.
If you don't like tin how about calculating the freezing point of water from
the laws of Quantum Mechanics? There is lots more about this in a article in
the August 23 1996 issue of Science by Seth Lloyd called "Universal Quantum
Simulators".
John K Clark johnkc@well.com
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBNRinUX03wfSpid95AQEhrQTww5k41fMlHxHXwtyZ/Dv8VitL4EtS11nU
6tvFwngiZ1usowCRnD5Q/vyZKbWQJLrtY9taIUNxukGD0ijrFTjn/kZp0AcMLucD
o4bg3kkOuHxBN8jUIUvIJ1K+NgMF/ReyePco9YdSfxwKuVc1o0sBDjIunB9yfYj+
/ytWQjiYiEycSA8HSUBXLnkVRrNeWwLpalgBibAxg9bi1v0aMZI=
=GYfv
-----END PGP SIGNATURE-----