Quantum computers are alluring but nobody has built one yet and until very
recently the only useful program known to be able to run on these machines
was one to factor large numbers for code breaking. Unfortunately there are
problems, to factor a 100 digit number the machine would need to perform
millions of quantum logical operations without being effected by the outside
environment, even with the newly discovered quantum error correcting codes
that would not be easy to do, not for that many operations. In the August 23
1996 Science is a fascinating research article by Seth Lloyd called
"Universal Quantum Simulators". Lloyd has found a way for quantum computers
to do something far, FAR, more useful than factoring numbers, and is much
easier for the machines to do too.
In quantum mechanics it's often possible in theory to predict what something
will do but not in practice because of computational complexity, that's why
Chemists must still perform experiments. To simulate the behavior of N
electrons, in a conventional computer you would need memory space and
computation time proportional to 2^2N. Just to figure out what's going on with
40 electrons, like those found in a medium sized atom, you would need to
perform 10^24 operations. It's no wonder that Chemists keep their test tubes.
Lloyd found a way to perform the same simulation using just N quantum bits
(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 a Analog computer. A very important
feature of Lloyd's algorithm is that it doesn't demand that the Quantum
computer be a perfect machine that is totally isolated from the environment,
it easily deals with errors. Incredibly, noise from the environment and
decoherence can be useful to the computer, it can actually help it simulate
noise and decoherence in the system it's simulating.
This may help put a stop to all the "End Of Science" books we've been seeing
lately. People were saying that it was a waste of time to try to find a
quantum theory of gravity because there would be no way to test it. It would
be a HUGE calculation, but a thousand qubit quantum computer could do it.
Lloyd says we could make a Quantum Computer today with a few tens of qubits
and it would "require only minor modifications of current technology".
I'd say that's a pretty good start. He also says "The wide variety of atomic,
molecular, and semiconductor quantum devices available suggests that quantum
simulation may soon be a reality".
In a separate development, Lov K Grover of ATT recently found a way for a
Quantum Computer to find a piece of information in a random list with N items
in just the square root of N steps, not 1/2 N steps, which is the average if
you do this on a conventional computer.
John K Clark johnkc@well.com
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBMjTzqn03wfSpid95AQHrlwTuI1eOux+ZvDsdYf4wwJRO73aZwg9ajbKq
IplLrR7+vIxN0Di3j7ir+NjdfOUtdx3jDe0+Y0DLfe26ajfy9HYmcKyGpdEMVM84
KAHnQB56aLmL5bWR1q7iZsgCMKH6C3XvV5Fyvk4Tt9DIXAhqx4XJ4NbHCOPrtt2j
9ysuvxJkMGpxYKw2Tg2pU3PrRYFX6Ghf7494+2B8alv/tTgR87g=
=K6vs
-----END PGP SIGNATURE-----