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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 was marked as an exact duplicate of an existing 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