Time+Place: Tuesday 07/11/2017 14:30 Room 337 Taub Bld.
Title: Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Speaker: Scott Aaronson - COLLOQUIUM LECTURE https://www.cs.utexas.edu/directory/scott-aaronson
Affiliation: University of Texas, Austin, Computer Science
Host: Yuval Filmus


In the near future, there will likely be special-purpose quantum
computers with 50 or so high-quality qubits.  In this talk, I'll
discuss general theoretical foundations for how to use such devices to
demonstrate "quantum supremacy": that is, a clear quantum speedup for
*some* task, motivated by the goal of overturning the Extended
Church-Turing Thesis (which says that all physical systems can be
efficiently simulated by classical computers) as confidently as

Based on recent joint work with Lijie Chen,  

Short Bio:
Scott Aaronson is David J. Bruton Centennial Professor of Computer
Science at the University of Texas at Austin.  He received his
bachelor's from Cornell University and his PhD from UC Berkeley, and
did postdoctoral fellowships at the Institute for Advanced Study as
well as the University of Waterloo.  Before coming to UT Austin, he
spent nine years as a professor in Electrical Engineering and Computer
Science at MIT.  Aaronson's research in theoretical computer science
has focused mainly on the capabilities and limits of quantum
computers.  His first book, Quantum Computing Since Democritus, was
published in 2013 by Cambridge University Press.  He has received 
the National Science Foundation's Alan T. Waterman Award, the United
States PECASE Award, the Vannevar Bush Fellowship, the Simons
Investigator award, and MIT's Junior Bose Award for Excellence in

Refreshments will be served from 14:15
Lecture starts at 14:30