Spring 2020

Quantum Supremacy I

Friday, January 31st, 2020 9:30 am10:30 am

Add to Calendar

This two-lecture tutorial will survey the complexity-theoretic foundations of quantum supremacy experiments. Topics will include: counting complexity, interference and #P vs Gap-P; worst-case exact sampling hardness results; average-case approximate sampling arguments and their recent extension to quantum random circuit sampling; Google's supremacy experiment and its verification; and alternative arguments for the hardness of these experiments.