Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Possible Duplicate:
What impact would P!=NP have on the characterization of BQP?

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.

Does P!=NP imply that NP-Complete problems cannot be solved in Quantum Polynomial time?

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?

share|cite|improve this question

marked as duplicate by François G. Dorais Aug 10 '10 at 19:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Is now really the best time for someone who does not usually care about it to ask these questions ? – David Lehavi Aug 10 '10 at 19:00
I'm closing as duplicate. It looks like the other question may reopen anyway... – François G. Dorais Aug 10 '10 at 19:08
I started studying quantum mechanics and algorithms recently and, yes, the recent news sparked the question. I do care about what I am studying and the potential evolutions of the field. – user8347 Aug 10 '10 at 19:10
The other question is now reopen. – François G. Dorais Aug 10 '10 at 19:17
@David Lehavi: Yes! When a big proof in computational complexity is announced, of course people are going to wonder how it will effect other big open problems. When Poincare came out, I was definitely asking my friends whether this gave a new algorithm for knot isomorphism. In this case, the question is at the right level for MO, so why not ask it here? (Of course, I don't know that unknown (yahoo) doesn't think about these issues all the time, but I am willing to tentatively assume he or she does not.) – David Speyer Aug 10 '10 at 19:17