[cryptography] D-Wave Sells First Quantum Computer

Nathan Loofbourrow njloof at gmail.com
Sat May 28 22:24:52 EDT 2011


On Sat, May 28, 2011 at 7:05 PM, James A. Donald <jamesd at echeque.com> wrote:

> On 28/05/11 03:37, James A. Donald wrote:
>
>> What can be said is that the class of problems soluble by a quantum
>>> computer
>>> is larger than the class of problems soluble by a classical computer.
>>>
>>
> On 2011-05-29 9:01 AM, David-Sarah Hopwood wrote:
>
>> No, it can't:
>>
>>  - for idealized quantum and classical computers (with unbounded memory
>>    running for unbounded time), those classes are identical.
>>
>>  - for quantum and classical computers that can be practically built at
>> any
>>    point in time, and with a limit on the time to find a solution, it
>>    certainly isn't clear that the class of problems soluble by quantum
>>    computers will be larger (ever). That depends on how big and fast you
>>    can make quantum computers and classical computers.
>>
>
> What can be said is that the class of problems soluble by a quantum
> computer with a polynomially large number of components in polynomial time
> is larger than the class of problems soluble by a classical computer with a
> polynomially large number of components in polynomial time.


Wait, was P!=NP proven and I missed it? I thought it was merely an assertion
with overwhelming evidence, but no formal proof.

n
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20110528/0bd380a0/attachment.html>


More information about the cryptography mailing list