Analysis of Quantum Algorithms with Classical Systems Counterpart

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

Views: 0 Downloads: 0


Shyam Sihare 1,* Dr. V V Nath 2

1. Department of Computer Science and Application, Dr. APJ Abdul Kalam Govt. College, Silvassa, Dadra & Nagar Haveli (UT)-396235, India

2. Institute of Management, Nirma University, Ahmedabad, Gujarat, India

* Corresponding author.


Received: 5 Nov. 2016 / Revised: 3 Dec. 2016 / Accepted: 25 Jan. 2017 / Published: 8 Mar. 2017

Index Terms

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


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


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