The Compendium of Super-Quadratic Computational Quantum Advantages
Philipp Kammerlander, Thomas E. O'Brien, Robbie King, Rolando D. Somma, Mária Kieferová, Brad Lackey, Alexander Schmidhuber, Siddhartha Jain, Andi Gu, Yuri Alexeev, Shouvanik Chakrabarti, Ruslan Shaydulin, Pietro M. Posta, Guang Hao Low, Dar Gilboa, Matthias Troyer, Barry C. Sanders, Matthias Christandl, Elica Kyoseva, Catherine Lefebvre, Ryan Babbush
quant-phSubmitted Oct 23, 2026• Announced Oct 26, 2026• 0 citations
This compendium presents a structured collection of computational problems with credible prospects for realizing meaningful quantum advantage, focused on describing problem characteristics rather than specific algorithms. It is intended for non-quantum researchers and practitioners with strong computational backgrounds, particularly domain experts, seeking to assess the relevance of quantum methods to real-world problems. The compendium focuses on enumerating core problems for which there is good evidence that a quantum computer can realize more than a quadratic speedup in offline non-relativized time-complexity (e.g., as opposed to in oracular settings, streaming models, or communication advantages). Entries characterize the structural constraints that real-world instances must satisfy to realize those advantages in practice. The intention is to provide a reference that can be leveraged to connect quantum algorithms to practical use cases.
This compendium presents a structured collection of computational problems with credible prospects for realizing meaningful quantum advantage, focused on describing problem characteristics rather than specific algorithms. It is intended for non-quantum researchers and practitioners with strong computational backgrounds, particularly domain experts, seeking to assess the relevance of quantum methods to real-world problems. The compendium focuses on enumerating core problems for which there is good evidence that a quantum computer can realize more than a quadratic speedup in offline non-relativized time-complexity (e.g., as opposed to in oracular settings, streaming models, or communication advantages). Entries characterize the structural constraints that real-world instances must satisfy to realize those advantages in practice. The intention is to provide a reference that can be leveraged to connect quantum algorithms to practical use cases.
Quantum computing has emerged as one of the most transformative technological developments of the twenty-first century. By exploiting the fundamental principles of quantum mechanics—namely superposition, entanglement, and measurement—quantum computers offer the potential to address problems that are beyond the practical reach of classical computing systems. As the field advances from theoretical exploration to real-world implementation, the demand for clear, structured, and comprehensive educational resources continues to grow. This book presents a systematic and accessible introduction to quantum computing, beginning with the essential concepts of classical information and computation and progressively advancing toward modern quantum algorithms and communication protocols. The initial chapters establish a strong foundation in classical bits, logic gates, Boolean algebra, reversible logic, and computational complexity, providing the conceptual bridge necessary to understand quantum computation. The discussion then moves to the quantum bit (qubit), examining its behavior through superposition, measurement, Bloch sphere representation, and physical realization. Special emphasis is placed on linear algebra as the mathematical framework underpinning quantum computing. Through this approach, readers are guided to develop an intuitive yet rigorous understanding of quantum states, quantum gates, and circuit-based computation. The text further extends these ideas to multi-qubit systems, quantum entanglement, universal gate sets, and quantum error correction, integrating theoretical principles with practical insights. To support experiential learning, the book incorporates hands-on exposure to leading quantum programming platforms, including IBM Quantum, OpenQASM, and Qiskit. These sections connect theory with practice, enabling readers to design, simulate, and execute quantum circuits on both simulators and real quantum hardware. Subsequent chapters explore key quantum communication protocols such as superdense coding, quantum teleportation, and quantum key distribution, followed by an in-depth treatment of foundational quantum algorithms including Deutsch–Jozsa, Grover’s search, Simon’s algorithm, and Shor’s factoring algorithm. This text is intended for undergraduate and postgraduate students, research scholars, and industry professionals seeking a coherent and structured pathway into quantum computing. No prior knowledge of quantum mechanics is assumed, although familiarity with linear algebra and classical computation will enhance comprehension. Each chapter is carefully organized to promote conceptual clarity, supported by illustrative examples, circuit diagrams, and concise summaries. Beyond explaining the principles and mechanisms of quantum computation, this book aims to inspire readers to engage with the future of the field—whether through academic research, industrial application, or interdisciplinary innovation. As quantum technologies continue to evolve, it is hoped that this text will serve as a dependable guide and a meaningful entry point into the quantum era.
Quantum computing has emerged as one of the most transformative technological developments of the twenty-first century. By exploiting the fundamental principles of quantum mechanics—namely superposition, entanglement, and measurement—quantum computers offer the potential to address problems that are beyond the practical reach of classical computing systems. As the field advances from theoretical exploration to real-world implementation, the demand for clear, structured, and comprehensive educational resources continues to grow. This book presents a systematic and accessible introduction to quantum computing, beginning with the essential concepts of classical information and computation and progressively advancing toward modern quantum algorithms and communication protocols. The initial chapters establish a strong foundation in classical bits, logic gates, Boolean algebra, reversible logic, and computational complexity, providing the conceptual bridge necessary to understand quantum computation. The discussion then moves to the quantum bit (qubit), examining its behavior through superposition, measurement, Bloch sphere representation, and physical realization. Special emphasis is placed on linear algebra as the mathematical framework underpinning quantum computing. Through this approach, readers are guided to develop an intuitive yet rigorous understanding of quantum states, quantum gates, and circuit-based computation. The text further extends these ideas to multi-qubit systems, quantum entanglement, universal gate sets, and quantum error correction, integrating theoretical principles with practical insights. To support experiential learning, the book incorporates hands-on exposure to leading quantum programming platforms, including IBM Quantum, OpenQASM, and Qiskit. These sections connect theory with practice, enabling readers to design, simulate, and execute quantum circuits on both simulators and real quantum hardware. Subsequent chapters explore key quantum communication protocols such as superdense coding, quantum teleportation, and quantum key distribution, followed by an in-depth treatment of foundational quantum algorithms including Deutsch–Jozsa, Grover’s search, Simon’s algorithm, and Shor’s factoring algorithm. This text is intended for undergraduate and postgraduate students, research scholars, and industry professionals seeking a coherent and structured pathway into quantum computing. No prior knowledge of quantum mechanics is assumed, although familiarity with linear algebra and classical computation will enhance comprehension. Each chapter is carefully organized to promote conceptual clarity, supported by illustrative examples, circuit diagrams, and concise summaries. Beyond explaining the principles and mechanisms of quantum computation, this book aims to inspire readers to engage with the future of the field—whether through academic research, industrial application, or interdisciplinary innovation. As quantum technologies continue to evolve, it is hoped that this text will serve as a dependable guide and a meaningful entry point into the quantum era.
Unlock the future of quantum technology with this comprehensive guide that bridges the gap between complex quantum theory and real-world applications, giving you the practical edge needed to solve the next generation’s toughest scientific and industrial problems. At its core, quantum computing leverages the principles of quantum mechanics to process information in fundamentally different ways from classical computing. As physical limits constrain the continued scaling of classical technologies, quantum computing offers a fundamentally new pathway toward solving complex problems in science, engineering, and industry. This book is a comprehensive guide designed to bridge the gap between theoretical principles and real-world quantum computing applications. It explores quantum information theory, a cornerstone of quantum computing, to explain how information is encoded, manipulated, and measured in a quantum system. Topics such as quantum gates, circuits, and the Bloch sphere representation are covered in detail, offering readers a solid grounding in the mechanics of quantum operations. With a focus on practical implementation, this book is tailored for students, researchers, and professionals seeking to delve into the transformative world of quantum computing, where the boundaries of classical computation are redefined. Readers will find the book: Uses step-by-step guides and hands-on tutorials for building quantum circuits and running algorithms; Explores core algorithms through detailed walkthroughs of quantum algorithms, including Shor’s, Grover’s, and Quantum Fourier Transform; Provides hands-on learning through exercises, coding challenges, and projects to reinforce practical skills. Audience Academics, researchers, quantum software developers and hardware engineers, data scientists, AI specialists, and security experts focused on the study and implementation of quantum systems and processors.
Abstract This guide is based on the IBM Quantum course Fundamentals of Quantum Algorithms and explores the computational advantages enabled by quantum information. The focus is on what can be achieved using a single quantum computer, rather than distributed quantum systems. The primary objective of the course is to analyze how quantum computation can outperform classical computation in specific problem classes. In particular, the material examines quantum query algorithms, which provide a structured framework for understanding quantum speedups. Key themes include: The conceptual foundations of quantum computational advantage. The role of superposition, interference, and entanglement in algorithm design. Query complexity and how quantum algorithms reduce the number of required oracle calls compared to classical approaches. Foundational algorithms that demonstrate provable quantum speedups. The central guiding question is: What advantages can a quantum computer potentially offer over a classical computer? Through hands-on experimentation on IBM Q, the work connects theoretical analysis with practical implementation, enabling deeper insight into how quantum resources translate into measurable computational gains.
Quantum algorithms with super-polynomial or polynomial speedups have been central to the promise of quantum computing, yet their real-world impact remains unclear because most analyses are asymptotic and worst-case. This work develops a systematic framework for characterizing practical quantum advantage that explicitly separates three components of speedup: (i) oracle/algorithmic advantage (Salg), (ii) data/instance structure advantage (Sdata), and (iii) implementability advantage under realistic noise and resource constraints (S impl). We first formalize quantum speedup as a triple (Salg, Sdata, S impl) that jointly captures theoretical complexity, distribution of input instances, and hardware feasibility. We then analyze seven canonical algorithms-Grover search, amplitude estimation, phase estimation, HHL, VQE, QAOA, and Hamiltonian simulationand extract common structural patterns that lead to genuine advantage over classical algorithms for specific problem families. Building on these patterns, we derive sufficient and necessary conditions for average-case quantum advantage in terms of problem symmetries, spectral properties, and data-access models. For NISQ-era devices, we incorporate realistic noise models and compilation overheads to define a practical advantage region in the space of problem size, error rates, and algorithm depth. The framework yields decision procedures and flowcharts that, given a candidate problem and hardware profile, can certify whether a proposed quantum algorithm is likely to achieve practical advantage or not. Case studies in finance (Monte Carlo risk analysis), chemistry (electronic structure estimation), and optimization (QAOA-type problems) illustrate how our method can guide algorithm and hardware co-design, and also show negative results where no advantage is achievable under realistic constraints. This work turns "quantum advantage" from a vague narrative into a quantitatively testable property of algorithmproblem-hardware triples.
As quantum computing approaches the threshold where certain tasks demonstrably outpace their classical machines, the need for a precise, clear, consensus-driven definition of quantum advantage becomes essential. Rapid progress in the field has blurred this term across companies, architectures, and application domains. Here, we aim to articulate an operational definition for quantum advantage that is both platform-agnostic and empirically verifiable. Building on this framework, we highlight the algorithmic families most likely to achieve early advantage. Finally, we outline our vision for the near future, in which quantum computers enhance existing high-performance computing platforms, enabling new frontiers in chemistry, materials discovery, optimization, and beyond.