Monday, November 27, 2017 at 4:00pm to 5:00pm
Rockefeller Hall, Schwartz Auditorium
General Physics Colloquium, Professor Scott Aaronson, University of Texas at Austin.
Refreshments from 3:30-3:50 pm
Title: Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Host: Paul Ginsparg
Abstract: 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 possible.
Based on recent joint work with Lijie Chen, https://arxiv.org/abs/1612.05903