4

The Deutsch-Josza problem provides an oracle separation between $\mathsf{EQP}$ (exact quantum-polynomial time) and $\mathsf{P}$, but there's no preclusion against adding randomization to get an efficient classical algorithm. For example, the Deutsch-Josza problem is trivially in $\mathsf{BPP}$. One could just make a small number of calls to the oracle; if ...


Only top voted, non community-wiki answers of a minimum length are eligible