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