Peter Wayner writes
Subject: Lecture-Peter Shor-Factoring in Poly time Date: Mon, 9 May 1994 02:23:57 GMT
FACTORING IN POLYNOMIAL TIME ON A QUANTUM COMPUTER Peter Shor, AT&T Bell Labs
Richard Feynman and others have challenged the traditional Turing machine model of computation. A new model of computation based on quantum mechanics has recently been proposed. It is too early to know whether quantum computers will be practical. However, it is shown that quantum computers can factor integers and compute discrete logarithms in polynomial time.
Lecture Hall D (north end), Goldwin Smith 11:40am, Monday, May 9
It is news to me that a quantum computer can do this, but is seems plausible that it could. Factoring is a member of a class of problems for which it is plausible that quantum computers have capabilities fundamentally superior to classical computers. On the other hand the field of quantum computing is full of crackpots. No quantum computers have been built. Quantum computers are unlikely to be useful until we get down to nanometer scale At the current rate of progress I conjecture (ill informed guestimate) that quantum computers will not do anything useful until about 2030. Quantum computers are coherence limited. For any computation that cannot be completed swiftly they will develop noise, which makes them act like classical computers. Thus even if their limitations are polynomial, whereas classical computers have non polynomial limitations on factoring, it will take them a long time to catch up with classical computers. Thus it will be many years after quantum computers have been developed and are being used routinely before they could equal classical computers in the factoring problem. If Goldwin's claim is true, then perhaps public key cryptograhy will eventually fall, in sixty years or so. -- --------------------------------------------------------------------- | We have the right to defend ourselves and our James A. Donald | property, because of the kind of animals that we | are. True law derives from this right, not from jamesd@netcom.com | the arbitrary power of the omnipotent state.