Special Issue — 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016); Guest Editors: Jarkko Kari and Alexander OkhotinNo Access

Grover’s Search with Faults on Some Marked Elements

Dmitry Kravchenko

Faculty of Computing, University of Latvia, Latvia

Search for more papers by this author

Nikolajs Nahimovs

Faculty of Computing, University of Latvia, Latvia

Search for more papers by this author

, and

Alexander Rivosh

Faculty of Computing, University of Latvia, Latvia

E-mail Address: alexander.rivosh@lu.lv

Search for more papers by this author

https://doi.org/10.1142/S0129054118410095Cited by:2 (Source: Crossref)

Abstract

Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ $N$ using $O (\sqrt{N})$ $O (\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm [3].

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 [2, 6].

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})$ $O (\sqrt{N})$ queries.

We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state $ρ_{l i m}$ $ρ_{l i m}$ .

Communicated by Jarkko Kari and Alexander Okhotin

Keywords:

References

1. A. Ambainis , Quantum search algorithms, SIGACT News, 35(2) :22–35, 2004. Crossref, Google Scholar
2. A. Ambainis, A. Backurs, N. Nahimovs and A. Rivosh , Grover’s algorithm with errors, Proceedings of MEMICS 2012, LNCS 7721 :180–189, 2013. Google Scholar
3. L. Grover , A fast quantum mechanical algorithm for database search, Proceedings of the 28th ACM STOC, 212–219, 1996. Google Scholar
4. R. Horn and C. Johnson , Matrix Analysis (Cambridge University Press, 2006). Google Scholar
5. P. Kaye, R. Laflamme and M. Mosca , An Introduction to Quantum Computing (Cambridge University Press, 2007). Google Scholar
6. O. Regev and L. Schiff , Impossibility of a Quantum Speed-up with a Faulty Oracle, Proceedings of ICALP’2008, LNCS 5125 :773–781, 2008. Google Scholar
7. I. Todhunter , Spherical Trigonometry (5th ed.). (MacMillan, 1886). Google Scholar