  Although the emergence of a fully-functional quantum computer may still be
far away from today, in the near future, it is possible to have medium-size,
special-purpose, quantum devices that can perform computational tasks not
efficiently simulable with any classical computer. This status is known as
quantum supremacy (or quantum advantage), where one of the promising approaches
is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic
quantum circuits has been argued to require an exponential time for classical
devices. A major question is whether quantum supremacy can be maintained under
noise without error correction, as the implementation of fault-tolerance would
cost lots of extra qubits and quantum gates. Here we show that, for a family of
chaotic quantum circuits subject to Pauli errors, there exists an
non-exponential classical algorithm capable of simulating the noisy chaotic
quantum circuits with bounded errors. This result represents a serious
challenge to a previous result in the literature suggesting the failure of
classical devices in simulating noisy chaotic circuits with about 48 qubits and
depth 25. Moreover, even though our model does not cover all types of
experimental errors, from a practical point view, our result describes a
well-defined setting where quantum supremacy can be tested against the
challenges of classical rivals, in the context of chaotic quantum circuits.
