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