Noise effects in the quantum search algorithm from the viewpoint of computational complexity

Piotr Gawron; Jerzy Klamka; Ryszard Winiarczyk

doi:10.2478/v10006-012-0037-2

.blurhash-client-img { display: none !important; }

Noise effects in the quantum search algorithm from the viewpoint of computational complexity

International Journal of Applied Mathematics and Computer Science

Volume 22 (2012): Issue 2 (June 2012)

By: Piotr Gawron, Jerzy Klamka and Ryszard Winiarczyk

Open Access

|Jun 2012

Abstract

We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search algorithm. We show that it is only for small amounts of noise that the quantum search algorithm is still more efficient than any classical algorithm.

References

Azuma, H. (2005). Higher-order perturbation theory for decoherence in Grover's algorithm, Physical Review A 72(4): 42305.10.1103/PhysRevA.72.042305
Search in Google Scholar
Barnes, J. P. and Warren, W. S. (1999). Decoherence and programmable quantum computation, Physical Review A 60(6): 4363-4374.10.1103/PhysRevA.60.4363
Search in Google Scholar
Bengtsson, I. and Życzkowski, K. (2006). Geometry of Quantum States. An Introduction to Quantum Entanglement, Cambridge University Press, Cambridge.10.1017/CBO9780511535048
Search in Google Scholar
Bouwmeester, D., Ekert, A. and Zeilinger, A. (2000). The Physics of Quantum Information: Quantum Cryptography, Quantum Teleportation, Quantum Computation, Physics and Astronomy Online Library, Springer, http://www.springer.com/physics/quantum+physics/book/978-3-540-66778-0. http://www.springer.com/physics/quantum+physics/book/978-3-540-66778-0
Search in Google Scholar
Bugajski, S. (2001). Quantum search, Archiwum Informatyki Teoretycznej i Stosowanej 13(2): 143-150.
Search in Google Scholar
Gawron, P., Klamka, J., Miszczak, J. A. and Winiarczyk, R. (2010). Extending scientific computing system with structural quantum programming capabilities, Bulletin of the Polish Academy of Sciences: Technical Sciences 58(1): 77-88.10.2478/v10175-010-0008-4
Search in Google Scholar
Grover, L. (1996). A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on the Theory of Computation, Philadelphia, PA, USA, pp. 212-219.
Search in Google Scholar
Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters 79(2): 325.10.1103/PhysRevLett.79.325
Search in Google Scholar
Grover, L. K. (1998). A framework for fast quantum mechanical algorithms, Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), Dallas, TX, USA, pp. 53-62.
Search in Google Scholar
Konstadakis, C. and Ellinas, D. (2001). Noisy Grover's Searching Algorithm, OSA Technical Digest Series, Optical Society of America, Rochester/New York, NY.
Search in Google Scholar
Long, G. L., Li, Y. S., Zhang, W. L. and Tu, C. C. (2000). Dominant gate imperfection in Grover's quantum search algorithm, Physical Review A 61(4): 42305.10.1103/PhysRevA.61.042305
Search in Google Scholar
Nielsen, M. and Chuang, I. (1999). Quantum Computation and Quantum Information, Cambridge University Press, Cambridge.
Search in Google Scholar
Pablo-Norman, B. and Ruiz-Altaba, M. (1999). Noise in Grover's quantum search algorithm, Physical Review A 61(1): 12301.10.1103/PhysRevA.61.012301
Search in Google Scholar
Salas, P. J. (2008). Noise effect on Grover algorithm, The European Physical Journal D 46(2): 365-373.10.1140/epjd/e2007-00295-1
Search in Google Scholar
Shapira, D., Mozes, S. and Biham, O. (2003). Effect of unitary noise on Grover's quantum search algorithm, Physical Review A 67(4): 42301.10.1103/PhysRevA.67.042301
Search in Google Scholar
Shenvi, N., Brown, K. R. and Whaley, K. B. (2003). Effects of a random noisy oracle on search algorithm complexity, Physical Review A 68(5): 52313.10.1103/PhysRevA.68.052313
Search in Google Scholar
Zhirov, O. V. and Shepelyansky, D. L. (2006). Dissipative decoherence in the Grover algorithm, The European Physical Journal D 38(2): 405-408.10.1140/epjd/e2006-00046-x
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.2478/v10006-012-0037-2 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X

Journal RSS Feed

Language: English

Page range: 493 - 499

Published on: Jun 28, 2012

Published by: University of Zielona Góra

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

Related subjects:

© 2012 Piotr Gawron, Jerzy Klamka, Ryszard Winiarczyk, published by University of Zielona Góra
This work is licensed under the Creative Commons License.

Volume 22 (2012): Issue 2 (June 2012)