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

Classical Simulation of quantum evolution on tree graphs

Yaoyun Shi, Luming Duan

Published Nov 8, 2005• 0 citations
OpenAlex

Abstract

We propose an efficient algorithm to classically simulate quantum evolution on tree graphs with bounded entanglement for any bipartite partition along an edge of the tree. The algorithm combines the Schmidt decomposition with the tensor network state, where the latter is a natural extension of the matrix product states from chains to graphs. As an interesting application of this algorithm, we show that any one-way quantum computation on tree graphs can be efficiently simulated with a classical computer.

Related papers

Classical simulation of quantum many-body systems with a tree tensor network

Yaoyun Shi, Luming Duan, Guifré Vidal

We show how to efficiently simulate a quantum many-body system with tree structure when its entanglement (Schmidt number) is small for any bipartite split along an edge of the tree. As an application, we show that any one-way quantum computation on a tree graph can be efficiently simulated with a classical computer.

arXiv:quant-ph/0511070•Physical Review A•Aug 23, 2006•577 citations

Entanglement growth and simulation efficiency in one-dimensional quantum lattice systems

Álvaro Perales, Guifré Vidal

We study the evolution of one-dimensional quantum lattice systems when the ground state is perturbed by altering one site in the middle of the chain. For a large class of models, we observe a similar pattern of entanglement growth during the evolution, characterized by a moderate increase of significant Schmidt coefficients in all relevant bipartite decompositions of the state. As a result, the evolution can be accurately described by a matrix product state and efficiently simulated using the time-evolving block decimation algorithm.

arXiv:0711.3676•Physical Review A•Oct 31, 2008•49 citations

Simulating quantum circuits using tree tensor networks

Philipp Seitz, Ismael Medina, Esther Cruz +2 more

We develop and analyze a method for simulating quantum circuits on classical computers by representing quantum states as rooted tree tensor networks. Our algorithm first determines a suitable, fixed tree structure adapted to the expected entanglement generated by the quantum circuit. The gates are sequentially applied to the tree by absorbing single-qubit gates into leaf nodes, and splitting two-qubit gates via singular value decomposition and threading the resulting virtual bond through the tree. We theoretically analyze the applicability of the method as well as its computational cost and memory requirements, and identify advantageous scenarios in terms of required bond dimensions as compared to a matrix product state representation. The study is complemented by numerical experiments for different quantum circuit layouts up to 37 qubits.

arXiv:2206.01000•Quantum•Mar 30, 2023•22 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

Classical simulation versus universality in measurement-based quantum computation

M. Van den Nest, Wolfgang Dür, Guifré Vidal +1 more

We investigate for which resource states an efficient classical simulation of measurement-based quantum computation is possible. We show that the Schmidt-rank width, a measure recently introduced to assess universality of resource states, plays a crucial role in also this context. We relate Schmidt-rank width to the optimal description of states in terms of tree tensor networks and show that an efficient classical simulation of measurement-based quantum computation is possible for all states with logarithmically bounded Schmidt-rank width (with respect to the system size). For graph states where the Schmidt-rank width scales in this way, we efficiently construct the optimal tree tensor network descriptions, and provide several examples. We highlight parallels in the efficient description of complex systems in quantum information theory and graph theory.

arXiv:quant-ph/0608060•Physical Review A•Jan 31, 2007•95 citations

Tree tensor network states represent low-energy states faithfully

Thomas Barthel

Extending corresponding results for matrix product states [Verstraete and Cirac, PRB 73, 094423 (2006); Schuch et al. PRL 100, 030504 (2008)], it is shown how the approximation error of tree tensor network states (TTNS) can be bounded using Schmidt spectra or Rényi entanglement entropies of the target quantum state. Conversely, one obtains bounds on TTNS bond dimensions needed to achieve a specific approximation accuracy. For tree lattices, the result implies that efficient TTNS approximations exist if $α<1$ Rényi entanglement entropies for single-branch cuts obey an area law, as in ground and low-energy states of certain gapped systems.

quant-pharXiv:2512.20215•Journal of Statistical Mechanics Theory and Experiment•Dec 24, 2025•0 citations
We propose an efficient algorithm to classically simulate quantum evolution on tree graphs with bounded entanglement for any bipartite partition along an edge of the tree. The algorithm combines the Schmidt decomposition with the tensor network state, where the latter is a natural extension of the matrix product states from chains to graphs. As an interesting application of this algorithm, we show that any one-way quantum computation on tree graphs can be efficiently simulated with a classical computer.
We study the evolution of one-dimensional quantum lattice systems when the ground state is perturbed by altering one site in the middle of the chain. For a large class of models, we observe a similar pattern of entanglement growth during the evolution, characterized by a moderate increase of significant Schmidt coefficients in all relevant bipartite decompositions of the state. As a result, the evolution can be accurately described by a matrix product state and efficiently simulated using the time-evolving block decimation algorithm.
We develop and analyze a method for simulating quantum circuits on classical computers by representing quantum states as rooted tree tensor networks. Our algorithm first determines a suitable, fixed tree structure adapted to the expected entanglement generated by the quantum circuit. The gates are sequentially applied to the tree by absorbing single-qubit gates into leaf nodes, and splitting two-qubit gates via singular value decomposition and threading the resulting virtual bond through the tree. We theoretically analyze the applicability of the method as well as its computational cost and memory requirements, and identify advantageous scenarios in terms of required bond dimensions as compared to a matrix product state representation. The study is complemented by numerical experiments for different quantum circuit layouts up to 37 qubits.
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.
We investigate for which resource states an efficient classical simulation of measurement-based quantum computation is possible. We show that the Schmidt-rank width, a measure recently introduced to assess universality of resource states, plays a crucial role in also this context. We relate Schmidt-rank width to the optimal description of states in terms of tree tensor networks and show that an efficient classical simulation of measurement-based quantum computation is possible for all states with logarithmically bounded Schmidt-rank width (with respect to the system size). For graph states where the Schmidt-rank width scales in this way, we efficiently construct the optimal tree tensor network descriptions, and provide several examples. We highlight parallels in the efficient description of complex systems in quantum information theory and graph theory.
Extending corresponding results for matrix product states [Verstraete and Cirac, PRB 73, 094423 (2006); Schuch et al. PRL 100, 030504 (2008)], it is shown how the approximation error of tree tensor network states (TTNS) can be bounded using Schmidt spectra or Rényi entanglement entropies of the target quantum state. Conversely, one obtains bounds on TTNS bond dimensions needed to achieve a specific approximation accuracy. For tree lattices, the result implies that efficient TTNS approximations exist if α<1α<1α<1 Rényi entanglement entropies for single-branch cuts obey an area law, as in ground and low-energy states of certain gapped systems.