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.
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.
Whether noisy quantum devices without error correction can provide quantum advantage over classical computers is a critical issue of current quantum computation. In this work, the random quantum circuits, which are used as the paradigm model to demonstrate quantum advantage, are simulated with depolarizing noise on experiment-relevant two-dimensional architecture. With comprehensive numerical simulation and theoretical analysis, we find that the maximum achievable operator entanglement entropy, which indicates maximal simulation cost, has area law scaling with the system size for constant noise rate. On the other hand, we also find that the maximum achievable operator entanglement entropy has power-law scaling with the noise rate for fixed system size, and the volume law scaling can be obtained only if the noise rate decreases when system size increase.
We aim to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods. Using operator entanglement entropy (OEE), we prove the following: (1) For single-qubit depolarizing noise on arbitrary circuits, tensor networks with poly(n) bond dimension suffice for fixed absolute Hilbert-Schmidt error after $\order{1}$ depth, while relative error demands $\order{\log n}$ depth; and this bound is optimal. (2) For single-qubit depolarizing noise on 1D local circuits, the existence of whole-trajectory error-bounded matrix product operator (MPO) of poly(n) bond dimension at all depths. (3) For general single-qubit noise in 1D brickwall circuits, random two-design gates with contraction coefficient c<1/3 yield an $\order{1}$ OEE plateau with probability 1−Te−Ω(n), while arbitrary gates with c<1/48 give $\order{\log n}$ OEE in the worst case. (4) In higher dimensions, these bounds yield uniform-in-depth poly(n) average boundary-bond dimensions for projected entangled pair operators~(PEPO) across every cut -- under depolarizing noise at either absolute or relative accuracy, and under general noise with strong contraction at absolute accuracy. Our results establish a rigorous connection between certain noise models, circuit types, and their classical simulability.
Simulating quantum circuits with classical computers requires resources growing exponentially in terms of system size.Real quantum computer with noise, however, may be simulated polynomially with various methods considering different noise models.In this work, we simulate random quantum circuits in one dimension with matrix product density operators (MPDOs), for different noise models such as dephasing, depolarizing, and amplitude damping.We show that the method based on matrix product states (MPSs) fails to approximate the noisy output quantum states for any of the noise models considered, while the MPDO method approximates them well.Compared with the method of matrix product operators (MPOs), the MPDO method reflects a clear physical picture of noise (with inner indices taking care of the noise simulation) and quantum entanglement (with bond indices taking care of two-qubit gate simulation).Consequently, in case of weak system noise, the resource cost of the MPDO will be significantly less than that of the MPO due to a relatively small inner dimension needed for the simulation.In case of strong system noise, a relatively small bond dimension may be sufficient to simulate the noisy circuits, indicating a regime that the noise is large enough for an "easy" classical simulation, which is further supported by a comparison with the experimental results on an IBM cloud device.Moreover, we propose a more effective tensor updates scheme with optimal truncations for both the inner and the bond dimensions, performed after each layer of the circuit, which enjoys a canonical form of the MPDO for improving simulation accuracy.With truncated inner dimension to a maximum value κ and bond dimension to a maximum value χ , the cost of our simulation scales as ∼NDκ 3 χ 3 , for an N-qubit circuit with depth D.
We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2O(d)loglog(n/δ) and n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
Matrix product states (MPSs) and matrix product operators (MPOs) have been proven to be a powerful tool to study quantum many-body systems but are restricted to moderately entangled states as the number of parameters scales exponentially with the entanglement entropy. While MPSs can efficiently find ground states of one-dimensional systems, their capacities are limited when simulating their dynamics, where the entanglement can increase ballistically with time. On the other hand, quantum devices appear as a natural platform to encode and perform the time evolution of correlated many-body states. However, accessing the regime of long-time dynamics is hampered by quantum noise. In this paper we use the best of worlds: the short-time dynamics is efficiently performed by MPSs, compiled into short-depth quantum circuits, and performed further in time on a quantum computer thanks to efficient MPO-optimized quantum circuits. We quantify the capacities of this hybrid classical-quantum scheme in terms of fidelities taking into account a noise model. We show that using classical knowledge in the form of tensor networks provides a way to better use limited quantum resources and lowers the noise requirements to reach a practical quantum advantage. Finally, we successfully demonstrate our approach with an experimental realization of the technique. Combined with efficient circuit transpilation we simulate a ten-qubit system on an actual quantum device over a longer time scale than low-bond-dimension MPSs and purely quantum Trotter evolution.
We study how matrix-product-operator (MPO) truncation errors evolve when simulating two setups: (1) 1D Haar-random circuits under either depolarizing noise or amplitude-damping noise, and (2) 1D Lindbladian dynamics of a non-integrable quantum Ising model under either depolarizing or amplitude-damping noise. We first show that the average purity of the system density matrix relaxes to a steady value on a timescale that scales inversely with the noise rate. We then show that truncation errors contract exponentially in both system size N and the evolution time t, as the noisy dynamics maps different density matrices toward the same steady state. This yields an empirical bound on the L1 truncation error that is exponentially tighter in N than the existing bound. Together, these results provide empirical evidence that MPO simulation algorithms may efficiently sample from the output of 1D noisy random circuits [setup (1)] at arbitrary circuit depth, and from the steady state of 1D Lindbladian dynamics [setup (2)].