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:2609.04165

Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography

Matthias C. Caro, Natalie McHugh, Sergii Strelchuk

quant-phcs.DScs.LGSubmitted Sep 3, 2026• Announced Sep 4, 2026• 0 citations
arXivHTMLPDF

Abstract

Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error $ε$ of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.

Comments
74 + 12 pages; 6 figures

Related papers

Proper Agnostic Learning of Matrix Product States and Tree Tensor Networks

Constantin Cedillo Vayson de Pradenne, Jordan Cotler

We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state $ρ$, our algorithms return a state $|ψ\rangle$ of chosen bond dimension such that $\langleψ| ρ|ψ\rangle$ is within $\varepsilon$ of the optimum over the model class, without assuming that $ρ$ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and $1/\varepsilon$, together with polynomial runtime in the system size for fixed local dimension, bond dimension, and accuracy. The same framework yields proper agnostic learning of tree tensor networks on bounded-degree trees, with both copy complexity and runtime polynomial in the system size when the remaining parameters are fixed.

quant-pharXiv:2609.30148•Sep 25, 2026•0 citations

Cost scaling of MPS and TTNS simulations for 2D and 3D systems with area-law entanglement

Thomas Barthel

Tensor network states are an indispensable tool for the simulation of strongly correlated quantum many-body systems. In recent years, tree tensor network states (TTNS) have been successfully used for two-dimensional systems and to benchmark quantum simulation approaches for condensed matter, nuclear, and particle physics. In comparison to the more traditional approach based on matrix product states (MPS), the graph distance of physical degrees of freedom can be drastically reduced in TTNS. Surprisingly, it turns out that, for large systems in $D>1$ spatial dimensions, MPS simulations of low-energy states are nevertheless more efficient than TTNS simulations. With a focus on $D=2$ and 3, the scaling of computational costs for different boundary conditions is determined under the assumption that the system obeys an entanglement (log-)area law, implying that bond dimensions scale exponentially in the surface area of the associated subsystems.

quant-pharXiv:2601.08132•Jan 14, 2026•0 citations

From tree tensor network to multiscale entanglement renormalization ansatz

Xiangjian Qian, Mingpu Qin

Tensor network states (TNSs) offer an efficient representation for the ground state of quantum many-body systems and play an important role in the simulations of them. Numerous TNSs have been proposed in the past few decades. However, due to the high cost of TNS for two-dimensional systems, a balance between the encoded entanglement and computational complexity of TNS is yet to be reached. In this work we introduce a new tree tensor network-based (TTN-based) TNS dubbed a ``fully augmented tree tensor network (FATTN) by releasing the constraint in augmented tree tensor network (ATTN). When disentanglers are augmented in the physical layer of TTN, FATTN can provide more entanglement than TTN and ATTN. At the same time, FATTN maintains the scaling of computational cost with bond dimension in TTN and ATTN. Benchmark results on the ground-state energy for the transverse Ising model are provided to demonstrate the improvement of accuracy of FATTN over TTN and ATTN. Moreover, FATTN is quite flexible, which can be constructed as an interpolation between TTN and the multiscale entanglement renormalization ansatz to reach a balance between the encoded entanglement and the computational cost.

arXiv:2110.08794•Physical review. B./Physical review. B•May 4, 2022•11 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

Tensor networks and geometry for the modelling of disordered quantum many-body systems

Andrew M. Goldsborough, Rudolf A. Römer

Tensor networks provide a powerful and elegant approach to quantum manybody simulation. The simplest example is the density matrix renormalisation group (DMRG), which is based on the variational update of a matrix product state (MPS). It has proved to be the most accurate approach for the numerical study of strongly correlated one dimensional systems. We use DMRG to study the one dimensional disordered Bose-Hubbard model at fillings N=L = 1=2, 1 and 2 and show that the whole phase diagram for each can be successfully obtained by analysing entanglement properties alone. We �nd that the average entanglement is insufficient to accurately locate all of the phases, however using the standard error on the mean we are able to construct a phase diagram that is consistent with previous studies. It has recently been shown that there is a connection between the geometry of tensor networks and the entanglement and correlation properties that it can encode, which is a generalisation of the so called area law for entanglement entropy. This suggests that whilst gapped quantum systems can be accurately modeled using an MPS, a tensor network with a holographic geometry is natural to capture the logarithmic entanglement scaling and power law decaying correlation functions of critical systems. We create an algorithm for the disordered Heisenberg Hamiltonian that self assembles a tensor network based on the disorder in the couplings. The geometry created is that of a disordered tree tensor network (TTN) that when averaged has the holographic properties characteristic of critical systems. We continue the analysis of holographic tensor network geometry by considering the average length of leaf-to-leaf paths in various tree graphs, which is related to two-point correlation functions in tensor networks. For regular, complete trees we analytically calculate the average path length and all statistical moments, and generalise it for any splitting number. We then turn to the Catalan trees, which is the set of unique binary trees with n vertices, as it has a similar geometry to the disordered TTNs. We calculate the average depth of a leaf and show that it is equal to the average path length. We compare these analytic results with the structures found in the TTN and randomly constructed trees to show that the renormalisation involved in the TTN algorithm is crucial in the selection of the tree structure.

•Sep 13, 2026•0 citations

Nearly Tight Bounds for Testing Tree Tensor Network States

Benjamin Lovitz, Angus Lowe

Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states, through a parameter known as the bond dimension. This leads to succinct representations of quantum many-body systems with a tree-like entanglement structure. In this work, we study the task of testing whether an unknown pure state is a TTNS onnqudits with bond dimension at mostr, or is far in trace distance from any such state. We first establish that, independent of the dimension of the state,O(nr2) copies suffice to accomplish this task with onesided error. We then prove that Ω(nr2/ logn) copies are necessary for any test with one-sided error wheneverr≥ 2 + logn. In particular, this closes a roughly quadratic gap in the previous bounds for testing matrix product states in this setting. On the other hand, whenr= 2 we show that Θ(√n) copies are both necessary and sufficient for the related task of testing whether a state is a product ofnbipartite states having Schmidt-rank at mostr, for some choice of the qudit dimensions. We also study the performance of tests using measurements performed on a small number of copies at a time. Here, we obtain new bounds for testing rank, Schmidt-rank, and TTNS when the tester is restricted to making measurements onr+ 1 copies of the state.

arXiv:2410.21417•IEEE Transactions on Information Theory•Mar 4, 2026•0 citations
Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state?
We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error εεε of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.
We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state ρρρ, our algorithms return a state ∣ψ⟩|ψ\rangle∣ψ⟩ of chosen bond dimension such that ⟨ψ∣ρ∣ψ⟩\langleψ| ρ|ψ\rangle⟨ψ∣ρ∣ψ⟩ is within ε\varepsilonε of the optimum over the model class, without assuming that ρρρ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and 1/ε1/\varepsilon1/ε, together with polynomial runtime in the system size for fixed local dimension, bond dimension, and accuracy. The same framework yields proper agnostic learning of tree tensor networks on bounded-degree trees, with both copy complexity and runtime polynomial in the system size when the remaining parameters are fixed.
Tensor network states are an indispensable tool for the simulation of strongly correlated quantum many-body systems. In recent years, tree tensor network states (TTNS) have been successfully used for two-dimensional systems and to benchmark quantum simulation approaches for condensed matter, nuclear, and particle physics. In comparison to the more traditional approach based on matrix product states (MPS), the graph distance of physical degrees of freedom can be drastically reduced in TTNS. Surprisingly, it turns out that, for large systems in D>1D>1D>1 spatial dimensions, MPS simulations of low-energy states are nevertheless more efficient than TTNS simulations. With a focus on D=2D=2D=2 and 3, the scaling of computational costs for different boundary conditions is determined under the assumption that the system obeys an entanglement (log-)area law, implying that bond dimensions scale exponentially in the surface area of the associated subsystems.
Tensor network states (TNSs) offer an efficient representation for the ground state of quantum many-body systems and play an important role in the simulations of them. Numerous TNSs have been proposed in the past few decades. However, due to the high cost of TNS for two-dimensional systems, a balance between the encoded entanglement and computational complexity of TNS is yet to be reached. In this work we introduce a new tree tensor network-based (TTN-based) TNS dubbed a ``fully augmented tree tensor network (FATTN) by releasing the constraint in augmented tree tensor network (ATTN). When disentanglers are augmented in the physical layer of TTN, FATTN can provide more entanglement than TTN and ATTN. At the same time, FATTN maintains the scaling of computational cost with bond dimension in TTN and ATTN. Benchmark results on the ground-state energy for the transverse Ising model are provided to demonstrate the improvement of accuracy of FATTN over TTN and ATTN. Moreover, FATTN is quite flexible, which can be constructed as an interpolation between TTN and the multiscale entanglement renormalization ansatz to reach a balance between the encoded entanglement and the computational cost.
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.
Tensor networks provide a powerful and elegant approach to quantum manybody simulation. The simplest example is the density matrix renormalisation group (DMRG), which is based on the variational update of a matrix product state (MPS). It has proved to be the most accurate approach for the numerical study of strongly correlated one dimensional systems. We use DMRG to study the one dimensional disordered Bose-Hubbard model at fillings N=L = 1=2, 1 and 2 and show that the whole phase diagram for each can be successfully obtained by analysing entanglement properties alone. We �nd that the average entanglement is insufficient to accurately locate all of the phases, however using the standard error on the mean we are able to construct a phase diagram that is consistent with previous studies. It has recently been shown that there is a connection between the geometry of tensor networks and the entanglement and correlation properties that it can encode, which is a generalisation of the so called area law for entanglement entropy. This suggests that whilst gapped quantum systems can be accurately modeled using an MPS, a tensor network with a holographic geometry is natural to capture the logarithmic entanglement scaling and power law decaying correlation functions of critical systems. We create an algorithm for the disordered Heisenberg Hamiltonian that self assembles a tensor network based on the disorder in the couplings. The geometry created is that of a disordered tree tensor network (TTN) that when averaged has the holographic properties characteristic of critical systems. We continue the analysis of holographic tensor network geometry by considering the average length of leaf-to-leaf paths in various tree graphs, which is related to two-point correlation functions in tensor networks. For regular, complete trees we analytically calculate the average path length and all statistical moments, and generalise it for any splitting number. We then turn to the Catalan trees, which is the set of unique binary trees with n vertices, as it has a similar geometry to the disordered TTNs. We calculate the average depth of a leaf and show that it is equal to the average path length. We compare these analytic results with the structures found in the TTN and randomly constructed trees to show that the renormalisation involved in the TTN algorithm is crucial in the selection of the tree structure.
Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states, through a parameter known as the bond dimension. This leads to succinct representations of quantum many-body systems with a tree-like entanglement structure. In this work, we study the task of testing whether an unknown pure state is a TTNS onnqudits with bond dimension at mostr, or is far in trace distance from any such state. We first establish that, independent of the dimension of the state,O(nr2) copies suffice to accomplish this task with onesided error. We then prove that Ω(nr2/ logn) copies are necessary for any test with one-sided error wheneverr≥ 2 + logn. In particular, this closes a roughly quadratic gap in the previous bounds for testing matrix product states in this setting. On the other hand, whenr= 2 we show that Θ(√n) copies are both necessary and sufficient for the related task of testing whether a state is a product ofnbipartite states having Schmidt-rank at mostr, for some choice of the qudit dimensions. We also study the performance of tests using measurements performed on a small number of copies at a time. Here, we obtain new bounds for testing rank, Schmidt-rank, and TTNS when the tester is restricted to making measurements onr+ 1 copies of the state.