INFORMATION CHANGE THE WORLD

International Journal of Information Engineering and Electronic Business(IJIEEB)

ISSN: 2074-9023 (Print), ISSN: 2074-9031 (Online)

Published By: MECS Press

IJIEEB Vol.9, No.2, Mar. 2017

Analysis of Quantum Algorithms with Classical Systems Counterpart

Full Text (PDF, 742KB), PP.20-26


Views:29   Downloads:0

Author(s)

Shyam R. Sihare, V V Nath

Index Terms

BQP(Bounded-error Quantum Polynomial time);BPP(Bounded-error Probabilistic Polynomial time);Quantum Algorithms;Classical Algorithms; Deutsch-Jozsa

Abstract

In this note, we look into two quantum algorithms, Deutsch-Josza’s and Shor’s algorithms. An attempt made to analyze classical as well as quantum parts computation. With that, analyze classical as well quantum parts complexities. 

Cite This Paper

Shyam R. Sihare, V V Nath,"Analysis of Quantum Algorithms with Classical Systems Counterpart", International Journal of Information Engineering and Electronic Business(IJIEEB), Vol.9, No.2, pp.20-26, 2017. DOI: 10.5815/ijieeb.2017.02.03

Reference

[1]Nielsen M. A., Chuang I. L.: Quantum Computation and Quantum Information. 3rd edn, Cambridge Press, UK, 2000

[2]David Deutsch: Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London A 400: 97, 1985 

[3]David Deutsch, Richard Jozsa: Rapid solutions of problems by quantum computation. Proceedings of the Royal Society of London A 439: 553, 1992

[4]Simon, D.R.: On the power of quantum computation. Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium, pp. 116–123, 1994

[5]Lov K. Grover:  A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 212–219, 1996.  arXiv:quant-ph/9605043

[6]Peter W. Shor: Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. pp. 124–134, 1994

[7]E.Horowitz, Sahni, D.Mehta: Fundamentals of Data Structures in C++. Galgotia Publications

[8]E. Bernstein, U. Vazirani: Quantum complexity theory. Proceeding of the 25th Annual ACM Symposium on Theory of Computing, pp. 11-20, 1993

[9]E. Bernstein, U. Vazirani: Quantum complexity theory. SIAM Journal on computing, 26(5), pp. 1411-1473, 1997

[10]Scott Aaronson: Quantum Complexity Theory; Lecture note 4.

[11]Pulak Ranjan Giri, Vladimir E. Korepin: A Review on Quantum Search Algorithms. pp. 1-43, 2016. http://arxiv.org/abs/1602.02730v

[12]Lomonaco, Jr: Shor's Quantum Factoring Algorithm. This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages, 2000 arXiv:quant-ph/0010034

[13]C.P. Williams, S.H. Clearwater: Explorations in Quantum Computing. 1998

[14]Arish Pitchai, A V Reddy, Nickolas Savarimuthu, Quantum Walk Algorithm to Compute Subgame Perfect Equilibrium in Finite Two-player Sequential Games, International Journal of Mathematical Sciences and Computing(IJMSC), Vol.2, No.3, pp.32-40, 2016.DOI: 10.5815/ijmsc.2016.03.03

[15]G. Brassard, N. Lütkenhaus, T. Mor, B. C. Sanders: Limitations on practical quantum cryptography. Physical Review Letters, 85(6):1330+, 2000

[16]Einstein A., B. Podolsky, N. Rosen: Can Quantum-Mechanical Description of Physical Reality be Considered Complete? Physical Review 47 (10), pp. 777–780, 1935