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 · IEEE Conference on Computational Complexity (CCC)

Complexity Limitations on Quantum Computation

Lance Fortnow, John D. Rogers

Published Oct 1, 1999• 189 citations
arXivHTMLPDF
DOI
10.1109/ccc.1998.694606

Related papers

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•8 citations

Quantum computational complexity

Daowen Qiu

Elsevier eBooks•Aug 29, 2025•0 citations

Quantum Computational Complexity

John Watrous

Springer eBooks•Nov 2, 2011•55 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•6 citations

Recent Progress in Quantum Computational Complexity

Andrew Chi-Chih Yao

Lecture notes in computer science•Jan 1, 2006•0 citations

Quantum Computing Algorithms and Their Emerging Applications in Complex Scientific Problems

Hira Fatima, Waqar Ahmad

Quantum computing (QC) presents transformative potential for solving complex scientific problems that remain intractable for classical computers. Leveraging quantum superposition, entanglement, and interference, quantum algorithms such as Shor’s factoring algorithm, Grover’s search algorithm, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA) enable exponential or polynomial speedups for selected problem classes. This paper explores recent advancements in quantum computing algorithms, their practical implementations, and emerging applications in fields such as molecular simulations, material science, cryptography, optimization, and machine learning. We highlight the strengths and limitations of current approaches, present performance analyses through graphical comparisons, and discuss prospective directions for integrating quantum algorithms into real-world scientific workflows. Our findings demonstrate that quantum computing is gradually transitioning from theoretical frameworks to experimental platforms capable of addressing highly complex computational challenges.

International Research Journal of Advanced Science•Jun 30, 2025•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.
Quantum computing (QC) presents transformative potential for solving complex scientific problems that remain intractable for classical computers. Leveraging quantum superposition, entanglement, and interference, quantum algorithms such as Shor’s factoring algorithm, Grover’s search algorithm, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA) enable exponential or polynomial speedups for selected problem classes. This paper explores recent advancements in quantum computing algorithms, their practical implementations, and emerging applications in fields such as molecular simulations, material science, cryptography, optimization, and machine learning. We highlight the strengths and limitations of current approaches, present performance analyses through graphical comparisons, and discuss prospective directions for integrating quantum algorithms into real-world scientific workflows. Our findings demonstrate that quantum computing is gradually transitioning from theoretical frameworks to experimental platforms capable of addressing highly complex computational challenges.