Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cs/9811023 · Journal of Computer and System Sciences

Complexity Limitations on Quantum Computation

Lance Fortnow, John D. Rogers

Published Oct 1, 1999• 171 citations
arXivHTMLPDF
DOI
10.1006/jcss.1999.1651

Related papers

The complexity of quantum computation

孝志 三原

•Jan 1, 1997•0 citations

Quantum Artificial Intelligence: Some Strategies and Perspectives

Marco Baioletti, Fabrizio Fagiolo, Corrado Appice Annalisa Malerba Donato Loglisci +4 more

In the twenty-first century, humanity is compelled to face global challenges. Such challenges involve complex systems. However, science has some cognitive and predictive limits in dealing with complex systems. Some of these limits are related to computational complexity and the recognition of variable patterns. To overcome these limits, artificial intelligence (AI) and quantum computing (QC) appear to be helpful. Even more promising is quantum AI (QAI), which emerged from the combination of AI and QC. The combination of AI and QC produces reciprocal, synergistic effects. This work describes some of these effects. It shows that QC offers new materials for implementing AI and innovative algorithms for solving optimisation problems and enhancing machine learning algorithms. Additionally, it demonstrates how AI algorithms can help overcome many of the experimental challenges associated with implementing QC. It also outlines several perspectives for the future development of quantum artificial intelligence.

AI•Aug 1, 2025•4 citations

Quantum Computational Complexity

John Watrous

Springer eBooks•Nov 2, 2011•47 citations

Empirical Investigation of Quantum Computing on Solving Complex Problems

Shahid Hussain, Yuba Neupane, Wenli Wang +3 more

Abstract Context: The rules of Quantum Mechanics have been exploited through Quantum Computing (QC) to solve specific problems and process information in expeditious ways as compared to Conventional Computing (CC) such as factoring integers. Problem: With the alluring computation capability of QC, it is still important to assess the implications and limitations of QC in solving a variety of computationally demanding problems. Method: In this regard, an empirical study was conducted to assess the efficacy of QC in terms of solving certain complex problems by keeping a tradeoff between the execution time and problem size. An analysis was performed based on the widely used Shor’s algorithms and the efficacy of QC as compared to CC was reported. Results: The outcomes show that QC has the potential to exponentially speed up the identification of a solution to certain polynomial problems that are intractable for CC. However, further research is needed to fully understand the potential and limitations of QC for Non-Polynomial (NP) complete problems.

Lecture notes in business information processing•Dec 27, 2023•3 citations

Quantum computational complexity

Daowen Qiu

Elsevier eBooks•Aug 29, 2025•0 citations

Quantum Limits, Computational Complexity and Philosophy – A Review

Tahir Ilyas

Quantum computing physics uses quantum qubits (or bits), for computer’s memory or processor. They can perform certain calculations much faster than a normal computer. The quantum computers have some limitations due to which the problems belonging to NP- Complete are not solved efficiently. This paper covers effective quantum algorithm for solving NP-Complete problems through some features of complexity theory, that we can simplify some of the philosophical interest problems.

Lahore Garrison University Research Journal of Computer Science and Information Technology•Apr 22, 2020•0 citations
In the twenty-first century, humanity is compelled to face global challenges. Such challenges involve complex systems. However, science has some cognitive and predictive limits in dealing with complex systems. Some of these limits are related to computational complexity and the recognition of variable patterns. To overcome these limits, artificial intelligence (AI) and quantum computing (QC) appear to be helpful. Even more promising is quantum AI (QAI), which emerged from the combination of AI and QC. The combination of AI and QC produces reciprocal, synergistic effects. This work describes some of these effects. It shows that QC offers new materials for implementing AI and innovative algorithms for solving optimisation problems and enhancing machine learning algorithms. Additionally, it demonstrates how AI algorithms can help overcome many of the experimental challenges associated with implementing QC. It also outlines several perspectives for the future development of quantum artificial intelligence.
Abstract Context: The rules of Quantum Mechanics have been exploited through Quantum Computing (QC) to solve specific problems and process information in expeditious ways as compared to Conventional Computing (CC) such as factoring integers. Problem: With the alluring computation capability of QC, it is still important to assess the implications and limitations of QC in solving a variety of computationally demanding problems. Method: In this regard, an empirical study was conducted to assess the efficacy of QC in terms of solving certain complex problems by keeping a tradeoff between the execution time and problem size. An analysis was performed based on the widely used Shor’s algorithms and the efficacy of QC as compared to CC was reported. Results: The outcomes show that QC has the potential to exponentially speed up the identification of a solution to certain polynomial problems that are intractable for CC. However, further research is needed to fully understand the potential and limitations of QC for Non-Polynomial (NP) complete problems.