Assuming P=BQP (ie we have polynomial time algorithms to solve all BQP problems) can we use it to prove that P=NP?

The argument is that since we have the Grover's algorithm which can solve NP complete problems with a quadratic speedup and since we have assumed that P=BQP, we can apply the Grovers algorithm repeatedly until it is reduced to a polynomial time problem.

  • 7
    $\begingroup$ The argument makes no sense to me. Grover’s algorithm does not solve any NP-complete problem, in fact it solves a P-problem, hence assuming P=BQP does not tell us anything about Grover’s algorithm that we don’t already know. More generally, P=BQP might mean that every problem solvable in time $n^c$ on quantum computer is solvable in time, say, $n^{42c}$ on a classical computer, hence it doesn’t imply anything about problems where we only have polynomial speed-up. $\endgroup$ – Emil Jeřábek Aug 9 '14 at 20:04

For what it’s worth, Fortnow and Rogers constructed an oracle relative to which P = BQP, but the polynomial hierarchy does not collapse (hence in particular P ≠ NP).



The statement "P=BQP" means that a quantum computer can be simulated efficiently (in polynomial time) on a classical computer. Since a quantum computer cannot solve NP-complete problems efficiently (at least not as far as we know), neither will a classical computer, so P=BQP will not help.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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