[Math] What impact would P=BQP have on NP

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.

Best Answer

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

Related Question