Quantum Heuristics: From Worst Case to Practice

Which problems allow for a quantum speedup, and which do not? This question lies at the heart of quantum information processing. Providing a definitive answer is challenging, as it connects deeply to unresolved questions in complexity theory. To make progress, complexity theory relies on conjectures such as P≠NP and the Strong Exponential Time Hypothesis, which suggest that for many computational problems, we have discovered algorithms that are asymptotically close to optimal in the worst case. While these hypotheses are invaluable for algorithmic thinking and design, they don't capture the whole picture. In practice, we are often interested in solving specific problem instances rather than finding universally efficient solutions. To bridge this gap, we need new tools and ideas. In this talk, I will explore the landscape from both theoretical and practical perspectives. On the theoretical side, I will introduce the concept of "queasy instances"—problem instances that are quantum-easy but classically hard (classically queasy). On the practical side, I will discuss how these insights connect to advancements in quantum hardware development and co-design.