  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.

Quantum Physics