[ExI] Quantum Computer Factoring

[John Clark]

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>