X-Message-Number: 6874
Date: Tue, 10 Sep 1996 10:14:46 -0700 (PDT)
From: John K Clark <>
Subject: SCI.CRYONICS Quantum Computers

-----BEGIN PGP SIGNED MESSAGE-----

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       

-----BEGIN PGP SIGNATURE-----
Version: 2.6.i

iQCzAgUBMjTzqn03wfSpid95AQHrlwTuI1eOux+ZvDsdYf4wwJRO73aZwg9ajbKq
IplLrR7+vIxN0Di3j7ir+NjdfOUtdx3jDe0+Y0DLfe26ajfy9HYmcKyGpdEMVM84
KAHnQB56aLmL5bWR1q7iZsgCMKH6C3XvV5Fyvk4Tt9DIXAhqx4XJ4NbHCOPrtt2j
9ysuvxJkMGpxYKw2Tg2pU3PrRYFX6Ghf7494+2B8alv/tTgR87g=
=K6vs
-----END PGP SIGNATURE-----


Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=6874