# What impact would P=BQP have on NP?

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.

• 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. – Emil Jeřábek Aug 9 '14 at 20:04

## 2 Answers

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).

No.

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.