[ExI] Quantum Computer Factoring
John Clark
johnkclark at gmail.com
Sat Dec 14 16:29:59 UTC 2019
On Sat, Dec 14, 2019 at 9:50 AM Brent Allsop via extropy-chat <
extropy-chat at lists.extropy.org> wrote:
*> I understand how to program a computer to factor number.*
> *But how is this done with a quantum computer?*
> *Is it all quantum hardware/configure? Or is some part of that software?*
> *And what would it mean to load a program into a quantum computer or what
> is it all about?*
> *Brent*
>
Every factoring algorithm ever discover that can be run on a conventional
computer runs in exponential time, that is to say the time it takes to
factor a number is proportional to 2^N where N is the number of digits in
the number you want to factor, so even a small increase in N could lead to
a huge increase in time. In 1994 Peter Shor found a algorithm that only
increased in polynomial time, that is to say the time it takes to factor a
number is proportional to N^2, a far slower rate. The only problem was that
Shor's Algorithm could only be run on a Quantum Computer but that problem
is less serious now than it was in 1994 and is becoming even less serious
every day.
Here is a explanation of how Shore's Algorithm works:
https://www.scottaaronson.com/blog/?p=208
John K Clark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20191214/8b975c9f/attachment.htm>
More information about the extropy-chat
mailing list