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

Piotr Gawron; Jerzy Klamka; Ryszard Winiarczyk

International Journal of Applied Mathematics and Computer Science (2012)

  • Volume: 22, Issue: 2, page 493-499
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Piotr Gawron, Jerzy Klamka, and Ryszard Winiarczyk. "Noise effects in the quantum search algorithm from the viewpoint of computational complexity." International Journal of Applied Mathematics and Computer Science 22.2 (2012): 493-499. <http://eudml.org/doc/208124>.

@article{PiotrGawron2012,
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.},
author = {Piotr Gawron, Jerzy Klamka, Ryszard Winiarczyk},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {quantum algorithms; quantum noise; algorithm complexity},
language = {eng},
number = {2},
pages = {493-499},
title = {Noise effects in the quantum search algorithm from the viewpoint of computational complexity},
url = {http://eudml.org/doc/208124},
volume = {22},
year = {2012},
}

TY - JOUR
AU - Piotr Gawron
AU - Jerzy Klamka
AU - Ryszard Winiarczyk
TI - Noise effects in the quantum search algorithm from the viewpoint of computational complexity
JO - International Journal of Applied Mathematics and Computer Science
PY - 2012
VL - 22
IS - 2
SP - 493
EP - 499
AB - 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.
LA - eng
KW - quantum algorithms; quantum noise; algorithm complexity
UR - http://eudml.org/doc/208124
ER -

References

top
  1. Azuma, H. (2005). Higher-order perturbation theory for decoherence in Grover's algorithm, Physical Review A 72(4): 42305. 
  2. Barnes, J.P. and Warren, W.S. (1999). Decoherence and programmable quantum computation, Physical Review A 60(6): 4363-4374. 
  3. Bengtsson, I. and Życzkowski, K. (2006). Geometry of Quantum States. An Introduction to Quantum Entanglement, Cambridge University Press, Cambridge. Zbl1146.81004
  4. 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. Zbl1008.81504
  5. Bugajski, S. (2001). Quantum search, Archiwum Informatyki Teoretycznej i Stosowanej 13(2): 143-150. 
  6. 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. 
  7. 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. Zbl0922.68044
  8. Grover, L.K. (1997). Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters 79(2): 325. 
  9. 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. Zbl1028.68055
  10. Konstadakis, C. and Ellinas, D. (2001). Noisy Grover's Searching Algorithm, OSA Technical Digest Series, Optical Society of America, Rochester/New York, NY. 
  11. 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. 
  12. Nielsen, M. and Chuang, I. (1999). Quantum Computation and Quantum Information, Cambridge University Press, Cambridge. Zbl1049.81015
  13. Pablo-Norman, B. and Ruiz-Altaba, M. (1999). Noise in Grover's quantum search algorithm, Physical Review A 61(1): 12301. 
  14. Salas, P.J. (2008). Noise effect on Grover algorithm, The European Physical Journal D 46(2): 365-373. 
  15. Shapira, D., Mozes, S. and Biham, O. (2003). Effect of unitary noise on Grover's quantum search algorithm, Physical Review A 67(4): 42301. 
  16. 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. 
  17. Zhirov, O.V. and Shepelyansky, D.L. (2006). Dissipative decoherence in the Grover algorithm, The European Physical Journal D 38(2): 405-408. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.