Are there any proofs that BQP is not in P? In laymen's terms, I am asking if there is any formal proof separating the complexity class that quantum computers are presently assumed to solve efficiently from the complexity class that non-quantum computers are presently known to solve efficiently.

Obviously I'm not talking here about black box/oracle proofs that show they are nonequivalent if we have access to some theoretical oracle. Just talking about regular, normal equivalence.


1 Answer 1


This is a famous open problem, so you won't find a proof anywhere at this time. We don't even know how to prove that $\mathsf{P\neq PSPACE}$, so finer separation of complexity classes such as $\mathsf{P\neq BQP}$ is also not known. Note that $\mathsf{BQP\subseteq PSPACE}$ is not trivial, you can find a proof in Quantum complexity theory, by Bernstein & Vazirani.

It is suspected that they are different, with the ability of quantum computers to factor integers in polynomial time being a strong witness.


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.