The Yamakawa-Zhandry breakthrough

QCCC Seminar

Daochen Wang (QuICS)
Wednesday, October 12, 2022 - 1:00pm
ATL 3100A and Virtual Via Zoom

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” ( and “Quantum Algorithms Conquer a New Kind of Problem” (Quanta magazine).