From postmaster@maxwell.lucifer.com Thu Dec 26 07:43:25 1996 Received: from maxwell.lucifer.com ([207.167.210.100]) by mail.nada.kth.se (8.6.10/8.6.10) with ESMTP id HAA26313 for ; Thu, 26 Dec 1996 07:43:19 +0100 Received: (from majordom@localhost) by maxwell.lucifer.com (8.7.5/8.7.3) id XAA19190 for extropians-outgoing; Wed, 25 Dec 1996 23:38:12 -0700 X-Authentication-Warning: maxwell.lucifer.com: majordom set sender to postmaster using -f Date: Wed, 25 Dec 1996 22:37:59 -0800 (PST) From: John K Clark Message-Id: <199612260637.WAA00288@well.com> To: extropians@lucifer.com Subject: COMPUTERS; Quantum Computers Sender: postmaster@extropy.org Precedence: bulk Reply-To: extropians@extropy.org Status: RO X-Status: -----BEGIN PGP SIGNED MESSAGE----- On Wed, 25 Dec 96 "David Musick" 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-----