# What impact would P!=NP have on the characterization of BQP?

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever solving NP-Complete problems in Quantum Polynomial time?

According to Wikipedia, quantum complexity classes BQP and QMA are the bounded-error quantum analogues of P and NP. Is it likely that a proof that $P\ne NP$ can be adapted to the quantum setting to show that $BQP \ne QMA?$

-
Evaluating the strength and reach of a proof "to be verified" of an incredibly hard question in a subtle and error-prone field... What could go wrong ;-? –  Simon Pepin Lehalleur Aug 10 '10 at 17:59
This primarilly depnds on the validity of the proof, an issue which is under intense discussion and which is not a suitable MO question at this time. –  Gil Kalai Aug 10 '10 at 18:07
I would take out the references to Deolalikar's proof, since it is not clear yet what it establishes. But the question of what impact $P \neq NP$ would have on $BQP$ is a perfectly good one, which I bet Scott Aaronson and Greg Kuperberg have lots to say about. I'm voting to reopen on that basis. –  David Speyer Aug 10 '10 at 18:47
I agree with David's assessment. –  David Hansen Aug 10 '10 at 18:49
I took the liberty of editing this question along the lines of OP's update and David's comment and voted to reopen. –  Victor Protsak Aug 10 '10 at 19:05