Spring 2020

Quantum Supremacy II

Friday, January 31st, 2020 11:00 am12:00 pm

Add to Calendar


Calvin Lab Auditorium

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.