On fault-tolerance of Grover's algorithm
Nikolajs Nahimovs, Alexander Rivosh, Dmitry Kravchenko · 2012
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size N in O( √ N ) queries, while any classical algorithm needs O(N ) queries [1]. However, if the query transformation might fail (with probability independent of the number of steps of the algorithm), then quantum speed-up disappears: no quantum algorithm can be faster than a classical exhaustive search by more than a constant factor [6]. In this paper we study the effect of a small number of failed queries. We show that k failed queries with a very high probability change the number of actually executed steps of Grover’s algorithm from l to O � l √ k