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/0411205

Classical simulation of quantum algorithms using the tensor product representation

Kawaguchi, A., Shimizu, K., 康弘 都倉, N. Imoto

Published Nov 30, 2004• 4 citations
arXivHTMLPDF

Abstract

Using the tensor product representation in the density matrix renormalization group, we show that a quantum circuit of Grover's algorithm, which has one-qubit unitary gates, generalized Toffoli gates, and projective measurements, can be efficiently simulated by a classical computer. It is possible to simulate quantum circuits with several ten qubits.

DOI
10.48550/arxiv.quant-ph/0411205

Related papers

Quantum Circuit Simulation Using the Density Matrix Renormalization Group

A. Kawaguchi

Simulating large quantum circuits with a classical computer requires enormous computational power, because the number of quantum states increases exponentially as a function of number of qubits. The density matrix renormalization group (DMRG) was introduced by White to study the properties of relatively large‐scale one‐dimensional quantum systems. This method corresponds to an efficient data compression for one‐dimensional quantum systems. In this study, we applied the DMRG method to quantum circuit simulation, and found that a simple quantum circuit based on Grover’s algorithm can be simulated with a classical computer.

AIP conference proceedings•Jan 1, 2004•0 citations

Simulating quantum circuits with tree tensor networks using density-matrix renormalization group algorithm

Aditya Dubey, Zeki Zeybek, Peter Schmelcher

Quantum computing offers the potential for computational abilities that can go beyond classical machines. However, they are still limited by several challenges such as noise, decoherence, and gate errors. As a result, efficient classical simulation of quantum circuits is vital not only for validating and benchmarking quantum hardware but also for gaining deeper insights into the behavior of quantum algorithms. A promising framework for classical simulation is provided by tensor networks. Recently, the density-matrix renormalization group (DMRG) algorithm was developed for simulating quantum circuits using matrix product states (MPS). Although MPS are efficient for representing quantum states with one-dimensional correlation structures, the fixed linear geometry restricts the expressive power of the MPS. In this work, we extend the DMRG algorithm for simulating quantum circuits to tree tensor networks (TTNs). The framework employs a variational compression scheme that optimizes the TTN to approximate the evolved quantum state. To benchmark the method, we simulate random circuits and the quantum approximate optimization algorithm (QAOA) with various two-qubit gate connectivities. For the random circuits, we devise treelike gate layouts that are suitable for TTN and show that TTN requires less memory than MPS for the simulations. For the QAOA circuits, a naive TTN construction that exploits graph structure significantly improves the simulation fidelities. Our findings show that the DMRG algorithm with TTNs provides a promising framework for simulating quantum circuits, particularly when gate connectivities exhibit clustering or a hierarchical structure.

arXiv:2504.16718•Physical review. B./Physical review. B•Aug 28, 2025•1 citation

Simulation of Matrix Product State on a Quantum Computer.

Amandeep Singh Bhatia, Mandeep Kaur Saggi

The study of tensor network theory is an important field and promises a wide range of experimental and quantum information theoretical applications. Matrix product state is the most well-known example of tensor network states, which provides an effective and efficient representation of one-dimensional quantum systems. Indeed, it lies at the heart of density matrix renormalization group (DMRG), a most common method for simulation of one-dimensional strongly correlated quantum systems. It has got attention from several areas varying from solid-state systems to quantum computing and quantum simulators. We have considered maximally entangled matrix product states (GHZ and W). Here, we designed the quantum circuits for implementing the matrix product states. In this paper, we simulated the matrix product states in customized IBM (2-qubit, 3-qubit and 4-qubit) quantum systems and determined the probability distribution among the quantum states.

arXiv:1811.09833•Nov 24, 2018•2 citations

Classical simulation of quantum circuits using a multiqubit Bloch vector representation of density matrices

Qunsheng Huang, Christian B. Mendl

In the Bloch sphere picture, one finds the coefficients for expanding a single-qubit density operator in terms of the identity and Pauli matrices. A generalization to $n$ qubits via tensor products represents a density operator by a real vector of length ${4}^{n}$, conceptually similar to a state vector. Here, we study this approach for the purpose of quantum circuit simulation, including noise processes. The tensor structure leads to computationally efficient algorithms for applying circuit gates and performing few-qubit quantum operations. In view of variational circuit optimization, we study ``backpropagation'' through a quantum circuit and gradient computation based on this representation, and generalize our analysis to the Lindblad equation for modeling the (nonunitary) time evolution of a density operator.

arXiv:2103.13962•Physical Review A•Feb 9, 2022•5 citations

Modelling of Grover’s quantum search algorithms: implementations of Simple quantum simulators on classical computers

Sergey Victorovich Ulyanov, Andrey G. Reshetnikov, Olga Tyatyushkina

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

System Analysis in Science and Education•Sep 30, 2020•4 citations

On the simulation of quantum circuits

Richard Jozsa

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.

arXiv:quant-ph/0603163•Mar 19, 2006•49 citations
Using the tensor product representation in the density matrix renormalization group, we show that a quantum circuit of Grover's algorithm, which has one-qubit unitary gates, generalized Toffoli gates, and projective measurements, can be efficiently simulated by a classical computer. It is possible to simulate quantum circuits with several ten qubits.
Simulating large quantum circuits with a classical computer requires enormous computational power, because the number of quantum states increases exponentially as a function of number of qubits. The density matrix renormalization group (DMRG) was introduced by White to study the properties of relatively large‐scale one‐dimensional quantum systems. This method corresponds to an efficient data compression for one‐dimensional quantum systems. In this study, we applied the DMRG method to quantum circuit simulation, and found that a simple quantum circuit based on Grover’s algorithm can be simulated with a classical computer.
Quantum computing offers the potential for computational abilities that can go beyond classical machines. However, they are still limited by several challenges such as noise, decoherence, and gate errors. As a result, efficient classical simulation of quantum circuits is vital not only for validating and benchmarking quantum hardware but also for gaining deeper insights into the behavior of quantum algorithms. A promising framework for classical simulation is provided by tensor networks. Recently, the density-matrix renormalization group (DMRG) algorithm was developed for simulating quantum circuits using matrix product states (MPS). Although MPS are efficient for representing quantum states with one-dimensional correlation structures, the fixed linear geometry restricts the expressive power of the MPS. In this work, we extend the DMRG algorithm for simulating quantum circuits to tree tensor networks (TTNs). The framework employs a variational compression scheme that optimizes the TTN to approximate the evolved quantum state. To benchmark the method, we simulate random circuits and the quantum approximate optimization algorithm (QAOA) with various two-qubit gate connectivities. For the random circuits, we devise treelike gate layouts that are suitable for TTN and show that TTN requires less memory than MPS for the simulations. For the QAOA circuits, a naive TTN construction that exploits graph structure significantly improves the simulation fidelities. Our findings show that the DMRG algorithm with TTNs provides a promising framework for simulating quantum circuits, particularly when gate connectivities exhibit clustering or a hierarchical structure.
The study of tensor network theory is an important field and promises a wide range of experimental and quantum information theoretical applications. Matrix product state is the most well-known example of tensor network states, which provides an effective and efficient representation of one-dimensional quantum systems. Indeed, it lies at the heart of density matrix renormalization group (DMRG), a most common method for simulation of one-dimensional strongly correlated quantum systems. It has got attention from several areas varying from solid-state systems to quantum computing and quantum simulators. We have considered maximally entangled matrix product states (GHZ and W). Here, we designed the quantum circuits for implementing the matrix product states. In this paper, we simulated the matrix product states in customized IBM (2-qubit, 3-qubit and 4-qubit) quantum systems and determined the probability distribution among the quantum states.
In the Bloch sphere picture, one finds the coefficients for expanding a single-qubit density operator in terms of the identity and Pauli matrices. A generalization to nnn qubits via tensor products represents a density operator by a real vector of length 4n{4}^{n}4n, conceptually similar to a state vector. Here, we study this approach for the purpose of quantum circuit simulation, including noise processes. The tensor structure leads to computationally efficient algorithms for applying circuit gates and performing few-qubit quantum operations. In view of variational circuit optimization, we study ``backpropagation'' through a quantum circuit and gradient computation based on this representation, and generalize our analysis to the Lindblad equation for modeling the (nonunitary) time evolution of a density operator.
Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.
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.