“Structure” has long played a central role in proposals for super-polynomial quantum advantage. This is especially true for problems whose solutions can be efficiently verified, where all prior results require algebraic computational conjectures or oracles with very specific features. In this talk, I will discuss a new approach for verifiable quantum advantage which, for a reasonable complexity-theoretic notion of “structure”, requires no structure at all.

* Joint work with Takashi Yamakawa

Panel discussion: Yael Kalai (Microsoft Research)Vinod Vaikuntanathan (MIT)Thomas Vidick (Caltech)Umesh Vazirani (UC Berkeley; moderator)

YouTube Video
Remote video URL
Remote video URL

All scheduled dates:


No Upcoming activities yet