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

Journal of automata, languages and combinatorics

Descriptional Complexity Issues in Quantum Computing

Jozef Gruska

Published Jan 1, 2000• 42 citations
Publisher

Abstract

The recent discovery that foundations of computing should be based on the laws of quantum physics brings new challenges also for descriptional complexity. The aim of the paper is to present and analyse these challenges, as well as the results obtained so far and the methods used to get them. The paper discusses also various open problems and research directions in quantum descriptional complexity to deal with.

DOI
10.25596/jalc-2000-191

Related papers

The quantum challenge to computer science

Philippe Jorrand

Information is physical: the laws which govern its encoding, processing and communication are bound by those of its unavoidably physical embodiment. In today's informatics, information obeys the laws of Newton's and Maxwell's classical physics: this assertion holds all the way from commercial computers down to (up to?) their most abstract models, e.g. Turing machines and lambda-calculus. Today's computation and communication are classical. Research in quantum information processing and communication was born some twenty five years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication based upon the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in cryptography, communications, information theory, algorithmics and, more recently, in abstract computational models, programming languages and semantics frameworks, have shown that this transplantation of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science.From a computer scientist's point of view, which is my point of view, I will explain the basics, survey the main achievements, and outline the current hot topics and major challenges of this promising and stimulating research. I will not assume any prior knowledge in quantum mechanics from the audience.

ACM International Conference on Computing Frontiers (CF)•May 7, 2007•0 citations

Quantum Computing: State-of-Art and Challenges

Juliana Kaizer Vizzotto

In this article we review the concept of quantum computing and briefly discuss the state-of-art and some actual challenges in the field of software (i.e. programming languages and algorithms) for quantum computing.

Workshop-School on Theoretical Computer Science•Oct 1, 2013•7 citations

Quantum Computing and Healthcare

Ritu Arya, Ashish Verma

The use of quantum computing1 in healthcare represents a significant shift with the potential to revolutionize medical research, diagnostics, and treatment. Quantum computing can process and analyze large datasets much faster than classical computing, offering new opportunities in healthcare. This paper examines the various ways quantum computing can be applied in healthcare, such as in drug discovery, genetic research, personalized medicine, and complex disease modeling. By using quantum algorithms, researchers can identify new treatment targets and simulate the effects of drugs on human biology in ways that were previously impossible, which can reduce the time and cost of bringing new drugs to market. Quantum computing also allows for analyzing large genomic datasets2, which can help tailor treatments to individual genetic profiles. Additionally, this technology helps in modeling complex biological systems and disease processes, providing insights into the mechanisms of diseases at a molecular level and enabling the development of more effective treatments. However, integrating quantum computing into healthcare comes with challenges such as technical limitations, the need for specialized expertise, data security concerns, and ethical considerations. This paper provides a comprehensive overview of the potential applications of quantum computing in healthcare, addresses the associated challenges, and discusses the future directions of this growing field, emphasizing the importance of interdisciplinary collaboration in fully utilizing quantum technologies in medicine. In recent years, quantum computing has rapidly advanced and attracted significant interest from academia and industry due to its unique ability to process information differently, resulting in previously unattainable computational capabilities. Despite its potential, the full impact of quantum computing on healthcare has not been thoroughly explored. This survey paper provides a systematic analysis of quantum computing's various capabilities in improving healthcare systems, focusing on its potential to transform compute-intensive healthcare tasks such as drug discovery, personalized medicine, DNA sequencing4, medical imaging5, and operational optimization. Through a comprehensive review of existing literature, we have developed taxonomies6 covering different aspects, including background and enabling technologies, applications, requirements, architectures, security, open issues, and future research directions, offering a comprehensive view of the quantum computing paradigm for healthcare. Our survey aims to assist new and experienced researchers in quantum computing and healthcare by helping them comprehend the current research landscape, identify potential opportunities and challenges, and make informed decisions when developing new architectures and applications for quantum computing in healthcare

International Journal of Advanced Research in Science Communication and Technology•Aug 30, 2024•8 citations

Towards An Architecture Description Language for Hybrid Quantum-Classical Systems

Jianjun Zhao

The rapid development of quantum computing technology has opened new possibilities for solving complex problems beyond the capabilities of classical computing paradigms. However, combining quantum computing with classical systems to create Hybrid Quantum-Classical (HQC) software systems presents unique challenges that require novel approaches in software architecture. This paper proposes a foundation for developing Architecture Description Languages (ADLs) specifically for HQC systems. We aim to provide a robust framework for coherently describing, integrating, and analyzing quantum and classical computing elements. The paper discusses the design principles, methodology, and structural components of the architecture description languages and outlines future research directions.

IEEE International Conference on Quantum Software (QSW)•Jul 7, 2024•4 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

Quantum Computing in Drug Discovery: A Review of Foundations and Emerging Applications

Sandeep Kulkarni, Dr. Pushpalata S. Patil, Ravindra D Patil

Research Problem: The traditional methods of drug discovery are time-consuming, costly, and at times ineffective. There is a need for more novel approaches that can enhance the processes of discovering new drugs and developing them into usable products. Objective of the Paper: This paper aims to conduct a review of the literature and find how the application of quantum computing can change the way drugs are discovered and processed in practice. Process of Review: The review process involved a comprehensive examination of the available literature and recent advances in the application of quantum computing to drug discovery. The review encompassed major studies, theories, and case studies related to the subject matter, aiming to identify the current state and potential future directions of the domain. Insights of the Review: 1. Primary Building Blocks: With quantum computing, superposition, entanglement, and other principles can be utilised to enable complex computations to be performed at higher speeds using less time than traditional computers. 2. Quantum modelling: Quantum computers are expected to accurately model the interactions of various molecules, which could result in the identification of viable drug candidates. 3. Drug Discovery Processes: Quantum algorithms are capable of faster processing than traditional methods when it comes to solving optimisation problems, such as protein structure prediction and molecular docking, in drug design. 4. Limitations and Challenges: As great as the promise of quantum computing is, it has its limitations and challenges, including hardware limitations, error rates, and the need for specialised algorithms. 5. Future Developments: The ongoing development of quantum hardware and algorithms is expected to enhance the practical applications of quantum computing in drug discovery, enabling the quicker and more cost-effective creation of new drugs.

International Journal of Advanced Pharmaceutical Sciences and Research•Jun 27, 2025•2 citations
The recent discovery that foundations of computing should be based on the laws of quantum physics brings new challenges also for descriptional complexity. The aim of the paper is to present and analyse these challenges, as well as the results obtained so far and the methods used to get them. The paper discusses also various open problems and research directions in quantum descriptional complexity to deal with.
Information is physical: the laws which govern its encoding, processing and communication are bound by those of its unavoidably physical embodiment. In today's informatics, information obeys the laws of Newton's and Maxwell's classical physics: this assertion holds all the way from commercial computers down to (up to?) their most abstract models, e.g. Turing machines and lambda-calculus. Today's computation and communication are classical. Research in quantum information processing and communication was born some twenty five years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication based upon the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in cryptography, communications, information theory, algorithmics and, more recently, in abstract computational models, programming languages and semantics frameworks, have shown that this transplantation of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science.From a computer scientist's point of view, which is my point of view, I will explain the basics, survey the main achievements, and outline the current hot topics and major challenges of this promising and stimulating research. I will not assume any prior knowledge in quantum mechanics from the audience.
The use of quantum computing1 in healthcare represents a significant shift with the potential to revolutionize medical research, diagnostics, and treatment. Quantum computing can process and analyze large datasets much faster than classical computing, offering new opportunities in healthcare. This paper examines the various ways quantum computing can be applied in healthcare, such as in drug discovery, genetic research, personalized medicine, and complex disease modeling. By using quantum algorithms, researchers can identify new treatment targets and simulate the effects of drugs on human biology in ways that were previously impossible, which can reduce the time and cost of bringing new drugs to market. Quantum computing also allows for analyzing large genomic datasets2, which can help tailor treatments to individual genetic profiles. Additionally, this technology helps in modeling complex biological systems and disease processes, providing insights into the mechanisms of diseases at a molecular level and enabling the development of more effective treatments. However, integrating quantum computing into healthcare comes with challenges such as technical limitations, the need for specialized expertise, data security concerns, and ethical considerations. This paper provides a comprehensive overview of the potential applications of quantum computing in healthcare, addresses the associated challenges, and discusses the future directions of this growing field, emphasizing the importance of interdisciplinary collaboration in fully utilizing quantum technologies in medicine. In recent years, quantum computing has rapidly advanced and attracted significant interest from academia and industry due to its unique ability to process information differently, resulting in previously unattainable computational capabilities. Despite its potential, the full impact of quantum computing on healthcare has not been thoroughly explored. This survey paper provides a systematic analysis of quantum computing's various capabilities in improving healthcare systems, focusing on its potential to transform compute-intensive healthcare tasks such as drug discovery, personalized medicine, DNA sequencing4, medical imaging5, and operational optimization. Through a comprehensive review of existing literature, we have developed taxonomies6 covering different aspects, including background and enabling technologies, applications, requirements, architectures, security, open issues, and future research directions, offering a comprehensive view of the quantum computing paradigm for healthcare. Our survey aims to assist new and experienced researchers in quantum computing and healthcare by helping them comprehend the current research landscape, identify potential opportunities and challenges, and make informed decisions when developing new architectures and applications for quantum computing in healthcare
The rapid development of quantum computing technology has opened new possibilities for solving complex problems beyond the capabilities of classical computing paradigms. However, combining quantum computing with classical systems to create Hybrid Quantum-Classical (HQC) software systems presents unique challenges that require novel approaches in software architecture. This paper proposes a foundation for developing Architecture Description Languages (ADLs) specifically for HQC systems. We aim to provide a robust framework for coherently describing, integrating, and analyzing quantum and classical computing elements. The paper discusses the design principles, methodology, and structural components of the architecture description languages and outlines future research directions.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Research Problem: The traditional methods of drug discovery are time-consuming, costly, and at times ineffective. There is a need for more novel approaches that can enhance the processes of discovering new drugs and developing them into usable products. Objective of the Paper: This paper aims to conduct a review of the literature and find how the application of quantum computing can change the way drugs are discovered and processed in practice. Process of Review: The review process involved a comprehensive examination of the available literature and recent advances in the application of quantum computing to drug discovery. The review encompassed major studies, theories, and case studies related to the subject matter, aiming to identify the current state and potential future directions of the domain. Insights of the Review: 1. Primary Building Blocks: With quantum computing, superposition, entanglement, and other principles can be utilised to enable complex computations to be performed at higher speeds using less time than traditional computers. 2. Quantum modelling: Quantum computers are expected to accurately model the interactions of various molecules, which could result in the identification of viable drug candidates. 3. Drug Discovery Processes: Quantum algorithms are capable of faster processing than traditional methods when it comes to solving optimisation problems, such as protein structure prediction and molecular docking, in drug design. 4. Limitations and Challenges: As great as the promise of quantum computing is, it has its limitations and challenges, including hardware limitations, error rates, and the need for specialised algorithms. 5. Future Developments: The ongoing development of quantum hardware and algorithms is expected to enhance the practical applications of quantum computing in drug discovery, enabling the quicker and more cost-effective creation of new drugs.