Abstract

This paper investigated the transformation that quantum computing brought into algorithmic complexity in the theoretical setting of computer science. This involved the appearance of new paradigm changes brought forth by quantum technologies, imposing on a glance at the performance of quantum algorithms in respect to classical models of computation regarding their effectiveness. Our contributions encompassed key quantum algorithms, specifically Shor's and Grover's algorithms, underlining the performance metrics of those algorithms. The mathematical modeling was supported by simulations using python libraries like Qiskit, which helped analyze the complexities of both algorithm types. From our simulations, it emerged that for smaller sizes of input, classical algorithms executed faster and illustrated their established efficiency. In contrast, quantum computing-algorithms like Grover's and Shor's - performed so much better for larger input sizes, showing potential advantages that may change the face of computational limitations. While promising much, it seemed from our findings that quantum computing would not show a quantum advantage for all computational tasks, because classical algorithms still remained robust and effective for many scenarios. This nuanced understanding underlines how complementary both the classical and quantum approaches are. Therefore, the insights gained through this work provide the basis for investigating where boundaries of computational capabilities evolve and what practical implications are of the integration of quantum technologies into existing systems.

Keywords

  • Quantum computing
  • algorithm complexity
  • Shor's algorithm
  • Grover's algorithm
  • classical algorithm

References

  1. 1. M. Moller, C. Vuik, “On the impact of quantum computing technology on future developments in high-performance scientific computing”, Ethics and Information Technology, vol. 19, pp. 253–269, Aug. 2017.
  2. 2. A. Holmes, S. Johri, G. Guerreschi, J. S. Clarke, and A. Y. Matsuura, “Impact of qubit connectivity on quantum algorithm performance”, Quantum Science and Technology, Mar. 2020.
  3. 3. J. R. Cruise, N. I. Gillespie, and B. Reid, “Practical Quantum Computing: The value of local computation”, Cornell University, Sep. 2020.
  4. 4. J. Singh, K. S. Bhangu, “Contemporary Quantum Computing Use Cases: Taxonomy, Review and Challenges”, Archives of Computational Methods in Engineering, vol. 30, pp. 615–638, Sep. 2023.
  5. 5. W. S. Ming, “The Role of Quantum Computing in Solving Complex Global Problems”, Hong Kong International Journal of Research Studies, vol. 1, no. 1, Dec. 2023.
  6. 6. S. Sharma, S. Solanki, and A. Yahya, Quantum Algorithms: Unleashing the Power of Quantum Computing, OORJA - International Journal of Management & IT, vol. 21, no. 1, p. 28, 2023.
  7. 7. P. N. Singh, S. Aarthi, “Quantum Circuits - An Application in Qiskit-Python”, 2021 Third International Conference on Intelligent Communication Technologies and Virtual Mobile Networks (ICICV), Mar. 2021.
  8. 8. D. C. McKay, T. Alexander, L. Bello, M. J. Biercuk, and others, “Qiskit Backend Specifications for OpenQASM and OpenPulse Experiments”, Cornell University, Sep. 2018.
  9. 9. N. M. Linke, D. Maslov, M. Roetteler, and C. Monroe, “Experimental comparison of two quantum computing architectures”, National Academy of Sciences, vol. 114, no. 13, pp. 3305-3310. Feb. 2017.
  10. 10. C. H. Ugwuishiwu, U. E. Orji, C. I. Ugwu, and C. N. Asogwa, “An overview of Quantum Cryptography and Shor’s Algorithm”, International Journal of Advanced Trends in Computer Science and Engineering, vol. 9, no. 5, pp. 748 -7495, Oct. 2020.
  11. 11. S. Fluhrer, “Reassessing Grover's Algorithm”, Cryptology ePrint Archive, Aug. 2017.
  12. 12. R. H. Preston, “Applying Grover's Algorithm to Hash Functions: A Software Perspective”, IEEE Transactions on Quantum Engineering, vol. 3, Jan. 2023.
  13. 13. S. Pattanayak, “Quantum Machine Learning with Python”, Apress, 2021.
  14. 14. N. Kanazawa, D. J. Egger, Y. Ben-Haim, H. Zhang, W. E. Shanks, G. Aleksandrowicz, and C. J. Wood, “Qiskit Experiments: A Python package to characterize and calibrate quantum computers”, The Journal of Open Source Software, Apr. 2023.
  15. 15. T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt, ”Realization of a scalable Shor algorithm”, Science, vol. 351, no. 6277, pp. 1068-1070, Mar. 2016.
  16. 16. R. L. Singleton Jr, M. L. Rogers, and D. L. Ostby, ‘Grover's Algorithm with Diffusion and Amplitude Steering”, Cornell University, Oct. 2021.
  17. 17. A. Mandviwalla, K. Ohshiro, B. Ji, “Implementing Grover’s Algorithm on the IBM Quantum Computers”, 2018 IEEE International Conference on Big Data, Dec. 2018.
  18. 18. A. Tulsi, “On the class of diffusion operators for fast quantum search”, Cornell University, Oct. 2016.
  19. 19. A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, “Quantum computing with Qiskit”, Cornell University, Jun. 2024.
  20. 20. IBM Quantum Documentation, “Circuit library” Angular, [Online]. Available: https://docs.quantum.ibm.com/guides/circuit-library. [Accessed: Jun. 21, 2024].
  21. 21. L. Burgholzer, R. Raymond, R. Wille, “Verifying Results of the IBM Qiskit Quantum Circuit Compilation Flow”, 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), Oct. 2020.
  22. 22. H. Y. Wong, “Shor’s Algorithm”, Introduction to Quantum Computing, pp. 289-298, Jun. 2023.
  23. 23. O. Dupouet, Y. Pitarch, M. Ferru, B. Bernela, “Community dynamics and knowledge production: forty years of research in quantum computing”, Journal of Knowledge Management, vol. 28, no. 3, Mar. 2024.
  24. 24. R. Wille, R. V. Meter, Y. Naveh, “IBM’s Qiskit Tool Chain: Working with and Developing for Real Quantum Computers”, 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), Mar. 2019.
  25. 25. V. Mavroeidis, K. Vishi, M. D. Zych, and A. Josang, “The Impact of Quantum Computing on Present Cryptography”, International Journal of Advanced Computer Science and Applications (IJACSA), vol. 9, no. 3, pp. 405-414, Mar. 2018.
  26. 26. J. Liu, D. Franklin, “Introduction to Quantum Computing for Everyone: Experience Report”, SIGCSE 2023: Proceedings of the 54th ACM Technical Symposium on Computer Science Education, vol. 1, pp. 1157-1163, Mar. 2023.
  27. 27. A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, “Quantum algorithms: A survey of applications and end-to-end complexities”, Cornell University, Oct. 2023.
  28. 28. D. Chawla, P. S. Mehra, “A Survey on Quantum Computing for Internet of Things Security”, Procedia Computer Science, vol. 218, pp. 2191-2200, 2023.
  29. 29. G. Guerreschi, M. Smelyanskiy, “Practical optimization for hybrid quantum-classical algorithms”, Cornell University, Jan. 2017.
  30. 30. C. T. Holter, P. Inglesant, M. Jirotka, “Reading the road: challenges and opportunities on the path to responsible innovation in quantum computing”, Technology Analysis & Strategic Management, vol. 35, no. 7, Sep. 2023.
  31. 31. J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, “The theory of variational hybrid quantum-classical algorithms”, New Journal of Physics, vol. 18, Feb. 2016.