[ExI] Quantum Computer Factoring

[Jason Resch]

Quantum computers are turning complete as quantum logic gates are
universal. However not every computation can be accelerated exponentially.

Jason

On Saturday, December 14, 2019, Brent Allsop via extropy-chat <
extropy-chat at lists.extropy.org> wrote:

> 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 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
>> _______________________________________________
>> 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/0899e28b/attachment.htm>