[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Shore on Quantum Computers
-----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 [email protected]
- -----------------------------------------------------------------------------
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 [email protected] Peter
Shor at AT&T Bell Laboratories, Murray Hill NJ
>In article <[email protected]>,
>[email protected] m (Arthur Rubin) writes: > In
><[email protected]> [email protected]
>([email protected]) 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-----