  We consider quantum search algorithms that have access to a noisy oracle
that, for every oracle call, with probability $p>0$ completely depolarizes the
query registers, while otherwise working properly. Previous results had not
ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even
for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query
complexity of the unstructured search is $\tilde\Theta(\max\{np,\sqrt{n}\})$.
The lower bound $\Omega(\max\{np,\sqrt n\})$ holds also for the dephasing noise
and even when, for every oracle call, the algorithm is provided with a flag
indicating whether the error has occurred.
