Quantum Search with Noisy Oracle

Abstract

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.

7 figures, 39 pages