Quantum random circuit sampling (RCS) is a basic primitive at the heart of recent "quantum supremacy" experiments. These experiments can be modeled as sampling from a random quantum circuit where each gate is subject to a small amount of noise. In this talk we give an overview of RCS and discuss recent progress on understanding its computational complexity.

We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.

Based on joint work with Dorit Aharonov, Xun Gao, Zeph Landau and Umesh Vazirani, arxiv: 2211.03999