# [ExI] Quantum Computer Factoring

Brent Allsop brent.allsop at gmail.com
Sun Dec 15 02:12:42 UTC 2019

```That helps, thanks.  But it doesn't seem anything like that would be
touring complete?

On Sat, Dec 14, 2019, 9:33 AM John Clark via extropy-chat <
extropy-chat at lists.extropy.org> wrote:

> 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
>> *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
> _______________________________________________
> extropy-chat mailing list
> extropy-chat at lists.extropy.org
> http://lists.extropy.org/mailman/listinfo.cgi/extropy-chat
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20191214/4221ef6a/attachment.htm>
```