The Yamakawa-Zhandry breakthrough
Speaker
Daochen Wang(QuICS)
Event Type
QCCC Seminar
Date & Time
October 12, 2022, 1:00pm
Where to Attend
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” (arxiv.org) and “Quantum Algorithms Conquer a New Kind of Problem” (Quanta magazine).