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.
Classical simulation of quantum circuits is an essential tool in quantum information science, but its applicability is constrained by the exponential growth of the Hilbert space and the entanglement structure of quantum states. In this work, we introduce Matrix Product Evolution (MPE), a tensor-train representation of quantum circuits constructed along the circuit depth rather than along the qubit index. Within this formulation, the simulation of a quantum circuit is modeled as the contraction of multiple MPE tensors. We develop an efficient contraction strategy based on a zip-up procedure to carry out this contraction in practice. We investigate the numerical behavior of this MPE-based contraction framework through simulations of random quantum circuits and the time evolution of a quantum many-body state. Our results characterize the growth of temporal bond dimensions, clarify how post-selection modifies the contraction cost and approximation accuracy, and identify regimes in which depth-oriented tensor-network contractions provide a useful complement to standard MPS-based simulation approaches.
We derive a rigorous upper bound on the classical computation time of finite-ranged tensor network contractions in d≥2 dimensions. Consequently, we show that quantum circuits of single-qubit and finite-ranged two-qubit gates can be classically simulated in subexponential time in the number of gates. Moreover, we present and implement an algorithm guaranteed to meet our bound and which finds contraction orders with vastly lower computational times in practice. In practically relevant cases this beats standard simulation schemes and, for certain quantum circuits, also a state-of-the-art method. Specifically, our algorithm leads to speedups of several orders of magnitude over naive contraction schemes for two-dimensional quantum circuits on as little as an 8×8 lattice. We obtain similarly efficient contraction schemes for Google's Sycamore-type quantum circuits, instantaneous quantum polynomial-time circuits, and nonhomogeneous (2+1)-dimensional random quantum circuits.
The study of quantum circuit simulation using classical computers is a key research topic that helps define the boundary of verifiable quantum advantage, solve quantum many-body problems, and inform development of quantum hardware and software. Tensor networks have become forefront mathematical tools for these tasks. Here we introduce a method to approximately simulate quantum circuits using sparsely-populated tensors. We describe a sparse tensor data structure that can represent quantum states with no underlying symmetry, and outline algorithms to efficiently contract and truncate these tensors. We show that the data structure and contraction algorithm are efficient, leading to expected runtime scalings versus qubit number and circuit depth. Our results motivate future research in optimization of sparse tensor networks for quantum simulation.
We present a method for classically simulating quantum circuits based on the tensor contraction model of Markov and Shi (e-print arXiv:quant-ph/0511069). Using this method we are able to classically simulate the approximate quantum Fourier transform in polynomial time. Moreover, our approach allow us to formulate a condition for the composability of simulable quantum circuits. We use this condition to show that any circuit composed of a constant number of approximate quantum Fourier transform circuits and log depth circuits with limited interaction range can also be efficiently simulated.
The study of quantum circuits composed of commuting gates is particularly useful to understand the delicate boundary between quantum and classical computation. Indeed, while being a restricted class, commuting circuits exhibit genuine quantum effects such as entanglement. In this paper we show that the computational power of commuting circuits exhibits a surprisingly rich structure. First we show that every 2-local commuting circuit acting on d-level systems and followed by single-qudit measurements can be efficiently simulated classically with high accuracy. In contrast, we prove that such strong simulations are hard for 3-local circuits. Using sampling methods we further show that all commuting circuits composed of exponentiated Pauli operators e^{iθP} can be simulated efficiently classically when followed by single-qubit measurements. Finally, we show that commuting circuits can efficiently simulate certain non-commutative processes, related in particular to constant-depth quantum circuits. This gives evidence that the power of commuting circuits goes beyond classical computation.