The power of noisy random quantum circuits*

In recent years, random quantum circuits have played a central role in the theory of quantum computation. Much of this prominence is due to the recent “quantum supremacy” experiment, which implemented random quantum circuits acting on 53 superconducting qubits. While random quantum circuits enjoy certain advantages that make them ideal for implementation by near-term quantum experiments, it is unclear a priori why they should be difficult to simulate classically. While we know several examples of quantum algorithms which attain exponential speedups over classical computation, they all seem to rely on highly structured circuits (such as quantum Fourier transforms) which are far from typical. Why then should we expect a generic quantum circuit to realize a large computational advantage?

In this talk, we discuss the computational difficulty of simulating random quantum circuit experiments from two perspectives: first we'll talk about classical hardness evidence. Second we'll talk about new classical simulation algorithms for noisy random quantum circuits in one dimension.

(This talk with be based on joint work with Adam Bouland, Chinmay Nirkhe and Umesh Vazirani, https://arxiv.org/abs/1803.04402, joint work with Kyungjoo Noh and Liang Jiang, https://arxiv.org/abs/2003.13163, and very recent joint work with Adam Bouland, Yunchao Liu and Zeph Landau)