Abstract
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, https://arxiv.org/abs/1803.044