The Compendium of Super-Quadratic Computational Quantum Advantages
Abstract
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.
Related
- Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
- Universal Computational Super-Resolution Framework for Imaging of Quantum Dots.
- Communication Advantages from Quantum Dense Network Coding
- Spatiotemporal quantum advantages for rare-event sampling
- Exponential quantum advantages for decoded quantum interferometry in the streaming setting
BibTeX
@misc{kammerlander2026compendium,
title = {{The Compendium of Super-Quadratic Computational Quantum Advantages}},
author = {Philipp Kammerlander and Thomas E. O'Brien and Robbie King and Rolando D. Somma and Mária Kieferová and Brad Lackey and Alexander Schmidhuber and Siddhartha Jain and Andi Gu and Yuri Alexeev and Shouvanik Chakrabarti and Ruslan Shaydulin and Pietro M. Posta and Guang Hao Low and Dar Gilboa and Matthias Troyer and Barry C. Sanders and Matthias Christandl and Elica Kyoseva and Catherine Lefebvre and Ryan Babbush},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32595},
eprint = {2610.32595},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32595},
}
RIS
TY - UNPB
TI - The Compendium of Super-Quadratic Computational Quantum Advantages
AU - Philipp Kammerlander
AU - Thomas E. O'Brien
AU - Robbie King
AU - Rolando D. Somma
AU - Mária Kieferová
AU - Brad Lackey
AU - Alexander Schmidhuber
AU - Siddhartha Jain
AU - Andi Gu
AU - Yuri Alexeev
AU - Shouvanik Chakrabarti
AU - Ruslan Shaydulin
AU - Pietro M. Posta
AU - Guang Hao Low
AU - Dar Gilboa
AU - Matthias Troyer
AU - Barry C. Sanders
AU - Matthias Christandl
AU - Elica Kyoseva
AU - Catherine Lefebvre
AU - Ryan Babbush
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32595
UR - https://arxiv.org/abs/2610.32595
AB - 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.
ER -