Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0603163

On the simulation of quantum circuits

Richard Jozsa

Published Mar 19, 2006• 100 citations
arXivHTMLPDF

Abstract

We consider recent works on the simulation of quantum circuits using the formalism of matrix product states and the formalism of contracting tensor networks. We provide simplified direct proofs of many of these results, extending an explicit class of efficiently simulable circuits (log depth circuits with 2-qubit gates of limited range) to the following: let C be any poly sized quantum circuit (generally of poly depth too) on n qubits comprising 1- and 2- qubit gates and 1-qubit measurements (with 2-qubit gates acting on arbitrary pairs of qubit lines). For each qubit line j let D_j be the number of 2-qubit gates that touch or cross the line j i.e. the number of 2-qubit gates that are applied to qubits i,k with i \leq j \leq k. Let D=max_j D_j. Then the quantum process can be classically simulated in time n poly(2^D). Thus if D=O(log n) then C may be efficiently classically simulated.

DOI
10.48550/arxiv.quant-ph/0603163

Related papers

Complexity of tensor network simulation for noisy quantum circuits

Yuguo Shao, Zishuo Zhao, Song Cheng +1 more

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 $\mathrm{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 $\mathrm{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 $\mathrm{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.

cond-mat.str-elCross-listedarXiv:2606.00474•Jun 2, 2026•2 citations

Matrix Product Evolution: A Method for Simulating Quantum Circuits Using Tensor Networks

Haruyuki Kawabe, Minoru Nagai, Tsuyoshi Okubo +1 more

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.

quant-pharXiv:2608.03472•Aug 5, 2026•0 citations

Approximate simulation of complex quantum circuits using sparse tensors

Benjamin N. Miller, Peter K. Elgee, Jason R. Pruitt +1 more

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.

quant-pharXiv:2602.04011•Feb 5, 2026•2 citations

Simulating Quantum Circuits Using Efficient Tensor Network Contraction Algorithms with Subexponential Upper Bound

Thorsten B. Wahl, Sergii Strelchuk

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.

arXiv:2208.01498•Physical Review Letters•Oct 30, 2023•15 citations

Efficient classical simulation of the approximate quantum Fourier transform

Nadav Yoran, Anthony J. Short

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.

arXiv:quant-ph/0611241•Physical Review A•Oct 16, 2007•58 citations

Classical Simulability of Quantum Circuits with Shallow Magic Depth

Y. Zhang, Yuxuan Zhang

Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log  ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.

arXiv:2409.13809•PRX Quantum•Feb 28, 2025•16 citations
We consider recent works on the simulation of quantum circuits using the formalism of matrix product states and the formalism of contracting tensor networks. We provide simplified direct proofs of many of these results, extending an explicit class of efficiently simulable circuits (log depth circuits with 2-qubit gates of limited range) to the following: let C be any poly sized quantum circuit (generally of poly depth too) on n qubits comprising 1- and 2- qubit gates and 1-qubit measurements (with 2-qubit gates acting on arbitrary pairs of qubit lines). For each qubit line j let D_j be the number of 2-qubit gates that touch or cross the line j i.e. the number of 2-qubit gates that are applied to qubits i,k with i \leq j \leq k. Let D=max_j D_j. Then the quantum process can be classically simulated in time n poly(2^D). Thus if D=O(log n) then C may be efficiently classically simulated.
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)\mathrm{poly}(n)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)\mathrm{poly}(n)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/3c<1/3c<1/3 yield an $\order{1}$ OEE plateau with probability 1−Te−Ω(n)1-Te^{-Ω(n)}1−Te−Ω(n), while arbitrary gates with c<1/48c<1/48c<1/48 give $\order{\log n}$ OEE in the worst case. (4) In higher dimensions, these bounds yield uniform-in-depth poly(n)\mathrm{poly}(n)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.
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 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.
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.
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log  ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.