Quantum Algorithms: A Survey of Applications and End-to-end Complexities
Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemysław Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G. S. L. Brandão
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.
The 1994 discovery of Shor's quantum algorithm for integer factorization—an important practical problem in the area of cryptography—demonstrated quantum computing's potential for real-world impact. Since then, researchers have worked intensively to expand the list of practical problems that quantum algorithms can solve effectively. This book surveys the fruits of this effort, covering proposed quantum algorithms for concrete problems in many application areas, including quantum chemistry, optimization, finance, and machine learning. For each quantum algorithm considered, the book clearly states the problem being solved and the full computational complexity of the procedure, making sure to account for the contribution from all the underlying primitive ingredients. Separately, the book provides a detailed, independent summary of the most common algorithmic primitives. It has a modular, encyclopedic format to facilitate navigation of the material and to provide a quick reference for designers of quantum algorithms and quantum computing researchers.
Quantum computing, grounded in the principles of superposition and entanglement, has emerged as a revolutionary paradigm with the potential to outperform classical systems in specific computational tasks. This paper presents a comprehensive survey of the foundational concepts, algorithmic developments, hardware architectures, and programming ecosystems in quantum computing. We analyze the current progress in key application areas such as cryptography, machine learning, optimization, and quantum chemistry. Furthermore, we review recent advances between 2023 and 2025, including developments in fault-tolerant architectures and quantum error correction. The paper also discusses the significant technical challenges that hinder large-scale practical deployment, including qubit scalability, decoherence, and programming limitations. By synthesizing literature across disciplines, this review aims to provide a holistic understanding of the quantum computing landscape and outline critical directions for future research and integration with classical systems.
Quantum computing is an emerging paradigm that leverages the principles of quantum mechanics to solve computational problems beyond the reach of classical computers. This article provides an overview of the fundamental concepts of qubits, the distinctive features of quantum mechanics such as superposition and entanglement, and the challenges of building scalable, fault-tolerant systems. It surveys key quantum algorithms and their potential applications in fields including cryptography, optimization, finance, chemistry, and machine learning. Additionally, it highlights the importance of verification frameworks for ensuring the reliability of quantum programs. A literature review of significant contributions is presented, drawing insights from recent surveys on quantum algorithms, qubit technologies, and software verification approaches. The article concludes by discussing ongoing challenges, such as error correction overhead, hardware scalability, and verification complexity, and suggests directions for future research.
Quantum machine learning combines quantum computing with machine learning to solve complex computational problems more efficiently than classical approaches. This survey provides an introduction to the foundations, algorithms, frameworks, data and applications of quantum machine learning, serving as a resource for researchers and practitioners. We begin by reviewing existing surveys to identify gaps that this work addresses, followed by a detailed discussion of the foundational principles of quantum mechanics and machine learning essential for quantum machine learning. Key algorithms are examined, highlighting their mechanisms, advantages, and applications across various domains. Current frameworks and platforms for implementing quantum machine learning algorithms are explored, emphasizing their unique features and suitability for different contexts. Existing quantum datasets for practical usage are also reported and commented on. This survey also reviews over 135 articles, categorized into theoretical and practical contributions, to identify key advances, limitations, and application areas within quantum machine learning. Critical challenges such as hardware limitations, error rates, and scalability are analyzed to detect the obstacles that must be addressed for practical deployment. By synthesizing these elements into a structured overview, this survey aims at serving as both an introduction and a guide for advancing research and development in this disruptive field.
This book, Quantum Computing: Algorithms, Architectures and Applications, has been carefully developed as a comprehensive resource to navigate the dynamic and complex world of quantum technologies. Intended for students, researchers, engineers, and technology enthusiasts, it aims to connect fundamental concepts with real-world implementation. The journey begins with the core principles of quantum mechanics relevant to computing, laying the groundwork that differentiates quantum systems from classical approaches. It further explores quantum gates, circuits, and computational logic, along with key topics such as error correction, system architectures, entanglement, superposition, and the no-cloning theorem. As the discussion progresses, the book examines foundational quantum algorithms, including the Deutsch–Jozsa algorithm, Simon’s problem, and others. These sections not only explain technical concepts but also encourage readers to rethink computational possibilities and limitations. The book also highlights practical applications and industry adoption. Quantum computing is increasingly influencing fields such as cryptography, finance, drug discovery, and climate science. Through global and regional case studies, readers gain insight into how various sectors are embracing this technological shift. A clear and structured approach has been maintained throughout, making the content accessible to beginners while still valuable for experienced professionals. The aim is to balance depth with clarity, ensuring both rigor and ease of understanding. While quantum computing continues to evolve with ongoing advancements and discoveries, the driving forces behind its progress remain curiosity, innovation, and collaboration.
Quantum algorithms have emerged as powerful computational tools that leverage the principles of quantum mechanics to address complex problems beyond the scope of classical computing. This chapter explores the foundational concepts, classifications, implementation challenges, and future prospects of quantum algorithms. Key breakthroughs such as Grover's and Shor's algorithms are explored alongside recent developments in quantum machine learning and optimization. The chapter also compares quantum and classical algorithmic complexity, highlighting areas of potential speedup. Practical limitations including hardware constraints, error correction, and resource estimation are critically analyzed. Finally, the chapter outlines emerging research directions and ethical considerations essential for responsible quantum computing development.