Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
