Grover’s Search with Faults on Some Marked Elements

DOI10.1007/978-3-662-49192-8_28zbMATH Open1442.68060arXiv1508.05108OpenAlexW2401756663MaRDI QIDQ5890527FDOQ5890527

Alexander Rivosh, Nikolajs Nahimovs, Dmitry Kravchenko

Publication date: 10 March 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(sqrtN)$ queries. It provides a significant speed-up over any classical algorithm cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs $Omega(N)$ queries to find a marked element cite{RS08}. cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in $O(sqrtN)$ queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state $h{o}_{lim}$.

Full work available at URL: https://arxiv.org/abs/1508.05108

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (1)

• Interaction-aided continuous time quantum search

This page was built for publication: Grover’s Search with Faults on Some Marked Elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890527)