From: John K Clark <johnkc@well.sf.ca.us>
Date: Mon, 23 May 94 22:06:04 PDT
To: cypherpunks@toad.com
Subject: Shore on Quantum Computers
Message-ID: <199405240505.WAA25147@well.sf.ca.us>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

I found this in sci.crypt, its by Peter Shore, the mathematician
who caused the resent excitement by finding a way to program a
quantum computer to factor numbers AND find discrete logarithms
in polynomial time. I realize nobody has even made a quantum
logic element yet, much less a working computer but the
implications are breathtaking.

                John K Clark                johnkc@well.sf.ca.us 

- -----------------------------------------------------------------------------

 Sun, 22 May 1994 11:24:13          sci.crypt               
Thread   20 of  102 Lines 32            Re: New Factoring Method
via Chaos?     Respno  18 of  19 shor@alice.att.com       Peter
Shor at AT&T Bell Laboratories, Murray Hill NJ

        >In article <a_rubin.769470113@dsg4.dse.beckman.com>,
        >a_rubin@dsg4.dse.beckman.co m (Arthur Rubin) writes: > In
        ><2rgh3l$rie@news.delphi.com> edfromnj@news.delphi.com
        >(EDFROMNJ@DELPHI.COM) writes: > > >This week's science news has
        >a good general article on quantum computing. > > ... > > >My
        >question is - could a quantum computer be simulated in software?
        >> > No. >

 I should try clearing up some of the misconceptions that are
multiplying on sci.crypt on quantum computers.  So far, the only
things quantum computers are known to do in polynomial time that
cannot be done on regular computers are a few contrived-looking
problems, factoring, and discrete logarithms.  In the original
mention of quantum computers, Feynman suggested they be used for
simulating quantum mechanics, and this is probably another case
they do better than regular computers.  Quantum computers can be
simulated by ordinary computers, but doing so (as far as we
know) entails an exponential factor in increased computation
time, so factoring via simulating a quantum computer will be
much slower than trial division (and you probably thought that
was the slowest algorithm possible for factoring (-: ).  Quantum
computing can be accomplished by the action of Schrodinger's
equation on a (somewhat complicated) Hamiltonian, where the
number of bits of precision for needed for the Hamiltonian is at
most logarithmic in the length of the computation, so it's not
cheating by using exponentially many bits.

Peter Shor

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCzAgUBLeGJt303wfSpid95AQH/qwTwhMh2NcIygoNE/GEHKxJZCoDWBX77lZR0
YsQt+gypIehDDOkIUgYbR0x4QDE5lcbSaErT3HJlCYPj0zgi6oPfBFzUjJh7Nndp
jUvzr6CcDeJ4d1EknFEiVeeB2kaDZtONpx61l5EIMldJ/pL54B/Gfg5blG2Lzz/g
vwhOVH8Vw8NjKpyjbyGZlJInRmYfNrWOD4tEm3oYr4VKGGEiThg=
=8Nbd
-----END PGP SIGNATURE-----