12
$\begingroup$

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?$

$\endgroup$
8
  • 2
    $\begingroup$ 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 ;-? $\endgroup$ Aug 10, 2010 at 17:59
  • $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Aug 10, 2010 at 18:07
  • 9
    $\begingroup$ 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. $\endgroup$ Aug 10, 2010 at 18:47
  • 2
    $\begingroup$ I agree with David's assessment. $\endgroup$ Aug 10, 2010 at 18:49
  • 4
    $\begingroup$ I took the liberty of editing this question along the lines of OP's update and David's comment and voted to reopen. $\endgroup$ Aug 10, 2010 at 19:05

2 Answers 2

13
$\begingroup$

David is right about one thing. Scott had a discussion about this on his blog and I was also involved.

On the one hand, many complexity theorists simply also assume that BQP does not contain NP, just as they assume that P does not contain NP. The evidence for the former is not as dramatic as that for the latter, but there is at least an oracle separation. I.e., there is an oracle A such that BQPA does not contain NPA. Now, there are some famous cases where two complexity classes are equal or there is an inclusion, even though there is also a credible oracle separation. But the oracle separations for BQP vs NP seem realistic. Besides, apart from tangible evidence, I for one consider BQP to be surprisingly powerful but not incredibly powerful. It's my intuition partly because I expect BQP to be realistic and I don't expect the universe to be perverse. I think of BQP as an extension of randomized computation based on quantum probability.

On the other hand, P vs PSPACE is already an unfathomable open problem. The two main barrier results for P vs NP, Baker-Gill-Solovay and Razborov-Rudich, apply to P vs PSPACE equally well. Since PSPACE contains both NP and BQP, if you were to show that either one does not equal P, then in particular you would show that PSPACE does not equal P. Actually, I don't know a good reason to try to prove that P ≠ NP rather than to first prove that P ≠ PSPACE, since the latter is at least formally easier.

$\endgroup$
2
  • 1
    $\begingroup$ You mean, "The evidence for the former is not as dramatic as that for the latter." $\endgroup$
    – Henry Yuen
    Aug 11, 2010 at 17:07
  • $\begingroup$ @GregKuperberg what is the realistic oracle that separates BQP and NP and how can you interpret quantum computing in terms of quantum probability? $\endgroup$
    – Turbo
    Mar 25, 2017 at 16:06
2
$\begingroup$

To your second question. It is unlikely that the current under-review proof of P != NP will allow you to seperate BQP and QMA (or BQP and P, or BQP and NP, or even BPP and NP...). Deolalikar's proof uses descriptive complexity, in particular it uses a correspondence between statements expressible in certain logics and the complexity classes P and NP. As far as I know there is no such nice one-to-one correspondences between BPP, BQP, or QMA and nice logics.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.