Verifiable Quantum Advantage Without Structure | Quantum Colloquium

“Structure” has long played a central role in proposals for superpolynomial 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 April 2022 talk from our Quantum Colloquium series, Mark Zhandry (Princeton University) discusses a new approach for verifiable quantum advantage that, for a reasonable complexity-theoretic notion of “structure," requires no structure at all. Based on joint work with Takashi Yamakawa (NTT).