On Sat, May 28, 2011 at 7:05 PM, James A. Donald <span dir="ltr"><<a href="mailto:jamesd@echeque.com">jamesd@echeque.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div class="im">On 28/05/11 03:37, James A. Donald wrote:<br>
</div><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


What can be said is that the class of problems soluble by a quantum computer<br>
is larger than the class of problems soluble by a classical computer.<br>
</blockquote></blockquote>
<br></div><div class="im">
On 2011-05-29 9:01 AM, David-Sarah Hopwood wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
No, it can't:<br>
<br>
  - for idealized quantum and classical computers (with unbounded memory<br>
    running for unbounded time), those classes are identical.<br>
<br>
  - for quantum and classical computers that can be practically built at any<br>
    point in time, and with a limit on the time to find a solution, it<br>
    certainly isn't clear that the class of problems soluble by quantum<br>
    computers will be larger (ever). That depends on how big and fast you<br>
    can make quantum computers and classical computers.<br>
</blockquote>
<br></div>
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.</blockquote>

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