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.
AI Summary
This compendium asks which computational problems have evidence for more-than-quadratic quantum time advantages and what conditions their instances must satisfy. It targets computational domain experts seeking application mappings, organizing problems rather than algorithms. Its scope excludes communication and streaming advantages, purely oracular separations without efficient instantiations, and quadratic speedups.
Entries describe the task, potential applications, classical and quantum complexities, evidence basis, and regimes of advantage. The collection separates Stage II—concrete, efficiently generable instance families expected to exhibit advantage—from Stage I primitives whose suitable instance families remain to be identified. It synthesizes existing algorithmic results, complexity-theoretic evidence, numerical studies, and experimental benchmarks rather than establishing a new speedup.
Examples include polynomial-time quantum factoring versus heuristic classical $\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$ scaling; decoded quantum interferometry for structured polynomial fitting; and planted-inference algorithms reducing a dominant classical $n^\ell$ cost to $n^{\ell/4}\operatorname{poly}(n)$ using guiding states, phase estimation, and amplitude amplification. The simulation discussion highlights higher-order out-of-time-order correlators, including a reported 65-qubit experimental benchmark, while classifying most other simulation tasks as Stage I.
The stated qualifications include moving classical baselines, restricted-model rather than general lower bounds, heuristic comparisons for QAOA, and dependence on input access, precision, state preparation, output extraction, and fault-tolerance overheads. Worst-case or asymptotic advantages need not apply to practical instances. Application spaces are generally proposed connections, not established end-to-end use cases; recent classical improvements already reduce some claimed comparisons.
Little sign of AI-generated textAI use disclosed
During the preparation and revision of this manuscript, the authors used generative-AI tools, including OpenAI ChatGPT, Anthropic Claude, and Google Gemini, to obtain critical feedback on structure, exposition, and selected technical claims.
Error found: The Exponential Congruences entry overlooks randomized classical membership-testing search followed by a finite-field discrete logarithm, reducing its advertised sixth-power and fourth-power examples to at most quadratic comparisons under the stated solution-density conditions.
The Jones Polynomial entry incorrectly uses random-braid unitary-design behavior as evidence for typical hardness of normalized additive matrix-entry approximation, although concentration makes returning zero accurate on almost all such instances.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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 asks which computational problems have evidence for more-than-quadratic quantum time advantages and what conditions their instances must satisfy. It targets computational domain experts seeking application mappings, organizing problems rather than algorithms. Its scope excludes communication and streaming advantages, purely oracular separations without efficient instantiations, and quadratic speedups.
Entries describe the task, potential applications, classical and quantum complexities, evidence basis, and regimes of advantage. The collection separates Stage II—concrete, efficiently generable instance families expected to exhibit advantage—from Stage I primitives whose suitable instance families remain to be identified. It synthesizes existing algorithmic results, complexity-theoretic evidence, numerical studies, and experimental benchmarks rather than establishing a new speedup.
Examples include polynomial-time quantum factoring versus heuristic classical exp(O((logN)1/3(loglogN)2/3)) scaling; decoded quantum interferometry for structured polynomial fitting; and planted-inference algorithms reducing a dominant classical nℓ cost to nℓ/4poly(n) using guiding states, phase estimation, and amplitude amplification. The simulation discussion highlights higher-order out-of-time-order correlators, including a reported 65-qubit experimental benchmark, while classifying most other simulation tasks as Stage I.
The stated qualifications include moving classical baselines, restricted-model rather than general lower bounds, heuristic comparisons for QAOA, and dependence on input access, precision, state preparation, output extraction, and fault-tolerance overheads. Worst-case or asymptotic advantages need not apply to practical instances. Application spaces are generally proposed connections, not established end-to-end use cases; recent classical improvements already reduce some claimed comparisons.
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.
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.
Identify, Transform, Benchmark, Show Quantum Advantage (ITBQ): Evaluating use cases for quantum computers. We introduce a four-step framework for assessing quantum computing applications -- from identifying relevant industry problems to demonstrating quantum advantage -- addressing steps often overlooked in the literature, such as rigorous benchmarking against classical solutions and the challenge of translating real-world tasks onto quantum hardware. Applying this framework to cases like NMR, multireference chemistry, and radicals reveals both significant opportunities and key barriers on the path to practical advantage. Our results highlight the need for transparent, structured criteria to focus research, guide investment, and accelerate meaningful quantum progress.