The Power of Random Quantum Circuits

          @misc{ scivideos_15623,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-150},
            author = {},
            keywords = {},
            language = {en},
            title = {The Power of Random Quantum Circuits},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {may},
            note = {15623 see, \url{https://scivideos.org/Simons-Institute/15623}}
          }
          

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.04402) 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, https://arxiv.org/abs/2003.13163).