[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Quantum Computers
-----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 [email protected]
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBMj9UEH03wfSpid95AQGa4wTwubIy9BE9emWFU1DVaDL7+o7p5Z86OVah
iBd3OKgONhJUmodDz5Egq7dwzqLvS2Rc5BQ7UPmT5uezzE/6wxmVDRAqxjJFKWHa
1TJtSv94d/S5HA8RjaAMWpOPOKQUf0KILy+jfoQMrpCLFd0cKM+aQUyhExPN92A7
EyIDQ3RUnAJNYR5JVXUVcEsiDVuPney56ZwkOqx1KAhuTI/Bcdg=
=AKnq
-----END PGP SIGNATURE-----