The Yamakawa-Zhandry breakthrough
Daochen Wang - University of Maryland
ATL 3100A and Virtual Via Zoom: https://umd.zoom.us/j/96508005344 Computer and Space Sciences Building (CSS)
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).
This talk is organized by Andrea F. Svejda