6533b81ffe1ef96bd127850e

RESEARCH PRODUCT

Grover’s Search with Faults on Some Marked Elements

Alexander RivoshNikolajs NahimovsDmitry Kravchenko

subject

Spherical trigonometryCombinatoricsUnit sphereQuantum queryComputer Science::Information RetrievalGrover's algorithmSearch problemSpace (mathematics)QuantumComputer Science::DatabasesRunning timeMathematics

description

Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size N using $$O\sqrt{N}$$ queries. It provides a significant speed-up over any classical algorithm [2]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [1, 4]. 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 marked elements in $$O\sqrt{N}$$ queries.

yearjournalcountryeditionlanguage
2016-01-01
https://doi.org/10.1007/978-3-662-49192-8_28