ISSN (Online): 2321-3418
server-injected
Engineering and Computer Science
Open Access

Investigating the Impact of Quantum Computing on Algorithmic Complexity

DOI: 10.18535/ijsrm/v12i10.ec01· Pages: 1467-1476· Vol. 12, No. 10, (2024)· Published: October 3, 2024
PDF
Views: 567 PDF downloads: 527

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 computingalgorithm complexityShor's algorithmGrover's algorithmclassical algorithm 1

References

  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.Google Scholar ↗
  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.Google Scholar ↗
  3. J. R. Cruise, N. I. Gillespie, and B. Reid, “Practical Quantum Computing: The value of local computation”, Cornell University, Sep. 2020.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  11. S. Fluhrer, “Reassessing Grover's Algorithm”, Cryptology ePrint Archive, Aug. 2017.Google Scholar ↗
  12. R. H. Preston, “Applying Grover's Algorithm to Hash Functions: A Software Perspective”, IEEE Transactions on Quantum Engineering, vol. 3, Jan. 2023.Google Scholar ↗
  13. S. Pattanayak, “Quantum Machine Learning with Python”, Apress, 2021.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  16. R. L. Singleton Jr, M. L. Rogers, and D. L. Ostby, ‘Grover's Algorithm with Diffusion and Amplitude Steering”, Cornell University, Oct. 2021.Google Scholar ↗
  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.Google Scholar ↗
  18. A. Tulsi, “On the class of diffusion operators for fast quantum search”, Cornell University, Oct. 2016.Google Scholar ↗
  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.Google Scholar ↗
  20. IBM Quantum Documentation, “Circuit library” Angular, [Online]. Available: https://docs.quantum.ibm.com/guides/circuit-library. [Accessed: Jun. 21, 2024].Google Scholar ↗
  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.Google Scholar ↗
  22. H. Y. Wong, “Shor’s Algorithm”, Introduction to Quantum Computing, pp. 289-298, Jun. 2023.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
  29. G. Guerreschi, M. Smelyanskiy, “Practical optimization for hybrid quantum-classical algorithms”, Cornell University, Jan. 2017.Google Scholar ↗
  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.Google Scholar ↗
  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.Google Scholar ↗
Author details
Mikita Piastou
✉ Corresponding Author
👤 View Profile →