From: John K Clark <johnkc@well.com>
Date: Wed, 18 Sep 1996 13:11:49 +0800
To: cypherpunks@toad.com
Subject: Quantum Computers
Message-ID: <199609180209.TAA16547@well.com>
MIME-Version: 1.0
Content-Type: text/plain


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

In the April 12 1996 issue of Science there is an article on
Quantum  Computers. It makes clear that a practical Quantum Computer 
has not been proven to be possible, nevertheless the article had a 
very optimistic tone, an optimism I did not see just one year ago. 
If such a machine could be built the ramifications are mind boggling.

When a conventional 64 bit single processor computer performs an
operation, it does it on ONE 64 bit number at a time. When a 64
bit (actually a 64 qubit) single processor QUANTUM computer
performs an operation it does it on ALL 64 bit numbers at the
same time, all 2^64 of them, more than a billion billion, 
and any increase in the number of qubits the computer can handle
will increase it's already astronomical power exponentially. 

It gets even wilder, because the quantum mechanical state of the
matter in the machine's memory determines the output, Seth Lloyd 
of MIT thinks you could run the machine in  reverse and the result 
would be a quantum mechanical micromanipulator.

Despite this enormous increase in performance and a possible
short cut to Nanotechnology, most weren't very interested because 
it didn't seem like a  Quantum Computer could ever be built. 
The slightest error or interaction with the outside environment would 
render the machine inoperative, conventional error correcting codes 
don't work for in the quantum domain and most said that correcting codes 
for quantum mechanical information was impossible. 
They were wrong.

Late last year Peter Shor of ATT showed how to encode a piece of
quantum  information in a 9 qubit system so that the information
is retained even if there is an error in one of the 9 qubits. 
A few months later researchers at IBM refined Shor's technique so that 
only 5 qubits was needed, and found  ways to correct for multiple errors. 
 
The trouble was, although Shor's idea worked  well for storing and 
transmitting quantum information without error, it did not work for the 
actual calculation, many thought that surely was impossible. 
It turns out they were wrong about that too.

In the August 30 1996 issue of Science is an article by J. I. Cira,  
T. Pellizzari, and P. Zoller entitled "Enforcing Coherent Evolution In  
Dissipative Quantum Dynamics". They propose a Quantum error correcting scheme 
with modest computational overhead that would dramatically increase the 
number of quantum logic gates the machine could have before errors made it 
unreliable. If p is probability that a single gate will fail, then without 
error correction a Quantum Computer can only have 1/p gates as a practical 
matter. With this new quantum error correcting code it can have 4/p^2 gates 
before errors overwhelm it. For example, if the probability that one gate 
will fail is .09 then if you have no error correction your Quantum Computer
better not have more that 11 logic gates, with this new error correcting idea 
it could have 494 logic gates without making more errors than the 11 did. 
 
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 an 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.
   
Apparently the appeal of making a calculation on 2^n numbers at the same time  
with a machine that only has n qbits is too strong for the military to ignore.  
In the same issue of Science is an article about the defense department  
making a 5 million dollar grant to start an institute for Quantum Information  
and Computing (QUIC).  It's charter has 5 aims.

1) Improve quantum algorithms.
2) Improve quantum logic gates. 
3) Improve the architecture of Quantum Computers. 
4) Improve quantum error correcting codes.
5) Study the general theory behind quantum computation.
                      
I find all this very exciting, it must have been like this in
the late 1930's when reports trickled in about nuclear fission
and the idea occurred to people that a bizarre device like a
nuclear bomb might actually be able to exist in the real world.
                                                

                                             John K Clark     johnkc@well.com

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

iQCzAgUBMj9UEH03wfSpid95AQGa4wTwubIy9BE9emWFU1DVaDL7+o7p5Z86OVah
iBd3OKgONhJUmodDz5Egq7dwzqLvS2Rc5BQ7UPmT5uezzE/6wxmVDRAqxjJFKWHa
1TJtSv94d/S5HA8RjaAMWpOPOKQUf0KILy+jfoQMrpCLFd0cKM+aQUyhExPN92A7
EyIDQ3RUnAJNYR5JVXUVcEsiDVuPney56ZwkOqx1KAhuTI/Bcdg=
=AKnq
-----END PGP SIGNATURE-----