most recent 30 from http://mathoverflow.net 2013-05-24T06:11:30Z http://mathoverflow.net/feeds/question/35159 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35159/quantum-computation-implications-of-p-vs-np unknown (yahoo) 2010-08-10T18:49:20Z 2010-08-10T18:49:20Z

<blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="http://mathoverflow.net/questions/35151/what-impact-would-pnp-have-on-the-characterization-of-bqp" rel="nofollow">What impact would P!=NP have on the characterization of BQP?</a> </p> </blockquote> <p>Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that P!=NP. This question is about the implications of P!=NP, not about the proof internals or specifics.</p> <p>Does P!=NP imply that NP-Complete problems cannot be solved in Quantum Polynomial time?</p> <p>According to Wikipedia, quantum complexity classes BQP and QMA which are the bounded-error quantum analogues of P and NP. If P!=NP was a know fact, does that imply that BQP!=QMA?</p>