|
4 |
arxiv tag
|
||
|
Post Reopened by Kevin Lin, David Speyer, David Hansen, Victor Protsak, Jonas Meyer
|
||||
|
|
||||
|
3 | better link to WP | ||
If What impact would P!=NP is proven, what is have on the implication towards characterization of 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 |
|
||

