Spring 2020

The Power of Random Quantum Circuits

Wednesday, May 6th, 2020 11:00 am11:50 am

Add to Calendar


Bill Fefferman (University of Chicago)


A critical goal for the field of quantum computing is quantum supremacy -- a demonstration of a quantum computation that is prohibitively hard for classical computers. Besides dispelling any skepticism about the experimental viability of quantum computers, quantum supremacy also provides a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth and recently implemented experimentally by the Google/UCSB team is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling (RCS).

In this talk we'll discuss the power of random quantum circuits from two perspectives.  First we'll talk about classical hardness evidence (joint work with Adam Bouland, Chinmay Nirkhe and Umesh Vazirani, and second we'll discuss very new easiness evidence concerning a restrictive subclass of random quantum circuits (joint work with Kyungjoo Noh and Liang Jiang,

PDF icon Talk Slides3.21 MB