From: John K Clark (johnkc@well.com)
Date: Wed Dec 25 1996 - 23:37:59 MST
-----BEGIN PGP SIGNED MESSAGE-----
On Wed, 25 Dec 96 "David Musick" <David_Musick@msn.com> Wrote:
>I don't know all that much about Quantum Computers.
I'm no expert on them either, the fact is there are no experts on Quantum
Computers, they're too new, everybody is stumbling around in the dark.
>John, could you please explain them a bit and then explain
>why they would bring about radical changes to the world?
The short answer is that although a conventional computer could (probably)
solve any problem a Quantum Computer could if it had enough time, a small
Quantum Computer, if a practical one could ever actually be made, could solve
problems almost instantly that would take a conventional computer, even a
Nanocomputer, many billions of years to solve. I hope you're not asking me
what changes this would bring to the world because I have no idea, but I
don't see how a machine of such cosmic power could leave the Universe
unchanged. Most of the following is a rehash of stuff I sent to the list
in the past year.
In the April 12 1996 issue of Science there is an article on Quantum
Computers. It makes clear that a Quantum Computer has not yet been proven to
be consistent with the laws of Physics, but 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, feed in information and change the state
of the memory, 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 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 were 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.
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.
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". His August 23 article is even more optimistic
than the April 12 article.
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
iQCzAgUBMsIh6n03wfSpid95AQE93ATw0Rh/k1NT8tlUZTMlVsGeRXFxALdbuA+e
fbEefA7YXchU9kNH1EYGMB56hQ6OMg2Tyi9+5TqgAbQck6NODaafn5FhpkofHmTk
pnRe3F8CHwbwQTD7bXlCZ4ke9rQcjf31whSRja0gHTvu5/Uiz9+jyifmprTPBZ4a
TJWZEEfy369lY0kFGJU4FryBb18cweZwxeVAtLvJ9C2i48SY7uo=
=n7T1
-----END PGP SIGNATURE-----
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:35:55 MST