International Journal of Information Engineering and Electronic Business (IJIEEB)
IJIEEB Vol. 9, No. 2, 8 Mar. 2017
Cover page and Table of Contents: PDF (size: 743KB)
Analysis of Quantum Algorithms with Classical Systems Counterpart
Full Text (PDF, 743KB), PP.20-26
Views: 0 Downloads: 0
Author(s)
Shyam Sihare
1,*
Dr. V V Nath
2
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