Recently, Yamakawa and Zhandry constructed a problem and proved that it admits a super-polynomial quantum speedup in the average case. Before their work, we only knew of problems that admit a super-polynomial quantum speedup in the worst case. In this talk, I will describe their problem and go over some key steps in their proof. I will also briefly discuss how their result can be construed as a non-interactive proof of quantumness relative to a random oracle.

References: “Verifiable Quantum Advantage without Structure” (arxiv.org) and “Quantum Algorithms Conquer a New Kind of Problem” (Quanta magazine).