Shore on Quantum Computers

[John K Clark]

-----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 at 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 at alice.att.com       Peter
Shor at AT&T Bell Laboratories, Murray Hill NJ

        >In article <a_rubin.769470113 at dsg4.dse.beckman.com>,
        >a_rubin at dsg4.dse.beckman.co m (Arthur Rubin) writes: > In
        ><2rgh3l$rie at news.delphi.com> edfromnj at news.delphi.com
        >(EDFROMNJ at 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-----