From: jamesd@netcom.com (James A. Donald)
Date: Mon, 9 May 94 22:39:36 PDT
To: pcw@access.digex.net (Peter Wayner)
Subject: Re: This is an abstract from a talk at Cornell University...
In-Reply-To: <199405100253.AA29544@access3.digex.net>
Message-ID: <199405100539.WAA12160@netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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.