MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 arxiv tag
Post Reopened by Kevin Lin, David Speyer, David Hansen, Victor Protsak, Jonas Meyer

# IfWhatimpactwould P!=NP isproven,whatishaveon the implicationtowardscharacterizationof BQP?

In the recent development where Deolalikar presented a (to be verified) proof

Many complexity theorists assume that P!=NP$P\ne NP.$ If this is proved, I began wondering of how such a proof 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 which are the bounded-error quantum analogues of P and NP. Is it likely that the a proof provided by Deolalikar that $P\ne NP$ can be adapted to the quantum setting and prove BQP!=QMA?

Edit Note: This question is not about the specifics of the current proof. My question is more about the implications of a generic P!=NP proof.to show that $BQP \ne QMA?$

Post Closed as "off topic" by Andrew Stacey, Gil Kalai, Noah Snyder, Steve Huntsman, Ryan Budney
2 added 150 characters in body
1