  Understanding the computational power of noisy intermediate-scale quantum
(NISQ) devices is of both fundamental and practical importance to quantum
information science. Here, we address the question of whether error-uncorrected
noisy quantum computers can provide computational advantage over classical
computers. Specifically, we study noisy random circuit sampling in one
dimension (or 1D noisy RCS) as a simple model for exploring the effects of
noise on the computational power of a noisy quantum device. In particular, we
simulate the real-time dynamics of 1D noisy random quantum circuits via matrix
product operators (MPOs) and characterize the computational power of the 1D
noisy quantum system by using a metric we call MPO entanglement entropy. The
latter metric is chosen because it determines the cost of classical MPO
simulation. We numerically demonstrate that for the two-qubit gate error rates
we considered, there exists a characteristic system size above which adding
more qubits does not bring about an exponential growth of the cost of classical
MPO simulation of 1D noisy systems. Specifically, we show that above the
characteristic system size, there is an optimal circuit depth, independent of
the system size, where the MPO entanglement entropy is maximized. Most
importantly, the maximum achievable MPO entanglement entropy is bounded by a
constant that depends only on the gate error rate, not on the system size. We
also provide a heuristic analysis to get the scaling of the maximum achievable
MPO entanglement entropy as a function of the gate error rate. The obtained
scaling suggests that although the cost of MPO simulation does not increase
exponentially in the system size above a certain characteristic system size, it
does increase exponentially as the gate error rate decreases, possibly making
classical simulation practically not feasible even with state-of-the-art
supercomputers.
