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.
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.
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.
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.
A random quantum circuit is a minimally structured model to study entanglement dynamics of many-body quantum systems. We consider a one-dimensional quantum circuit with noisy Haar-random unitary gates using density matrix operator and tensor contraction methods. It is shown that the entanglement evolution of the random quantum circuits is properly characterized by the logarithmic entanglement negativity. By performing exact numerical calculations, we find that, as the physical error rate is decreased below a critical value p c ≈ 0.056, the logarithmic entanglement negativity changes from the area law to the volume law, giving rise to an entanglement transition. The critical exponent of the correlation length can be determined from the finite-size scaling analysis, revealing the universal dynamic property of the noisy intermediate-scale quantum devices.
The process by which open quantum systems thermalize with an environment is both of fundamental interest and relevant to noisy quantum devices. As a minimal model of this process, we consider a qudit chain evolving under local random unitaries and local depolarization channels. After mapping to a statistical mechanics model, the depolarization (noise) acts like a symmetry-breaking field, and we argue that it causes the system to thermalize within a timescale independent of system size. We show that various bipartite entanglement measures---mutual information, operator entanglement, and entanglement negativity---grow at a speed proportional to the size of the bipartition boundary. As a result, these entanglement measures obey an area law: Their maximal value during the dynamics is bounded by the boundary instead of the volume. In contrast, if the depolarization only acts at the system boundary, then the maximum value of the entanglement measures obeys a volume law. We complement our analysis with scalable simulations involving Clifford gates, for both one- and two-dimensional systems.
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.
The Quantum Volume protocol uses scrambling random circuits to benchmark NISQ computers. Quantum Volume is generally well-regarded as a benchmark for small, noisy, quantum computers because it requires the quantum computer to implement many non-local entangling gates within a square-shaped circuit, which incentivizes high qubit count, long qubit coherence times, and low error rates on all hardware gates. Quantum Volume circuits inherently produce high-entanglement states that are fragile to errors and decoherence. The Quantum Volume benchmark measures an observable called heavy-output-probability (HOP), where an HOP of 0.5 corresponds to complete loss of coherence, and in the limit of system size an HOP ≈0.84 for a fully coherent quantum processor. Here, we numerically study the tradeoff between depolarizing noise, entanglement as quantified by the bipartite negativity measure, and HOP in quantum volume circuits. Our results contextualize prior small scale quantum volume demonstrations on quantum computers and highlight that under depolarizing noise, due to finite system size effects heavy output probabilities can be greater than 0.5 while the bipartite negativity entanglement has been destroyed. This implies, although improbable, that a NISQ computer could pass the Quantum Volume benchmark test threshold of 2/3 while the underlying quantum computation has no global entanglement -- albeit only for small n.