MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

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

share|cite|improve this answer
Thank you Emil for the reply – user22603 Aug 11 '14 at 7:26


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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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