[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Quantum Computers*From*: John K Clark <[email protected]>*Date*: Tue, 17 Sep 1996 19:09:10 -0700 (PDT)*Sender*: [email protected]

-----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-----

- Prev by Date:
**Re: Snake-Oil FAQ** - Next by Date:
**Re: The Expat Tax Is Law - The Door Is Now Closed!** - Prev by thread:
**Re: Systems/Communications Security Positions in the South Bay** - Next by thread:
**Re: Quantum Computers** - Index(es):