Beyond-classical computation from a computer science perspective

Abstract

Outperforming classical supercomputers in a well-defined computational task is an important milestone in the long-term quest for practical quantum computing. I will argue that this milestone has been reached for the task of random quantum circuit sampling. I will review recent advances in complexity theory and classical algorithms related to this experiment. BosonSampling is another important proposal for early beyond-classical demonstrations. I will review recent BosonSampling experiments and algorithms.