Quantum computers—devices that process information using quantum mechanical effects—have long been expected to outperform classical systems on certain tasks. Over the past few decades, researchers have worked to rigorously demonstrate such advantages, ideally in ways that are provable, verifiable and experimentally realizable.