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.
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.
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.
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 ∣ψ⟩ of chosen bond dimension such that ⟨ψ∣ρ∣ψ⟩ is within ε 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/ε, 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.
Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ1, …, k has rank r for each k ∊ {1, …, n}. When r = 1, this corresponds to the set of product states, i.e. states of the form |ψ1〉 ⊗ ⃛ ⊗ |ψn), which possess no entanglement. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state |ψ〉 is an MPS in the property testing model. In this model, one is given m identical copies of |ψ〉, and the goal is to determine whether |ψ〉 is an MPS of bond dimension r or whether |ψ〉 is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro [17], and a key ingredient in their proof that QMA(2) = QMA(k) for k ≥ 2. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in [17] and [23]. For the case of r ≥ 2, we give an efficient algorithm for testing whether |ψ〉 is an MPS of bond dimension r using m = O(nr2) copies, independent of the dimensions of the qudits, and we show that Ω(n1/2) copies are necessary for this task. This lower bound shows that a dependence on the number of qudits n is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.
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.
Tensor networks are used to efficiently approximate states of strongly-correlated quantum many-body systems. More generally, tensor network approximations may allow to reduce the costs for operating on an order-N tensor from exponential to polynomial in N, and this has become a popular approach for machine learning. We introduce the idea of imposing low-rank constraints on the tensors that compose the tensor network. With this modification, the time and space complexities for the network optimization can be substantially reduced while maintaining high accuracy. We detail this idea for tree tensor network states (TTNS) and projected entangled-pair states. Simulations of spin models on Cayley trees with low-rank TTNS exemplify the effect of rank constraints on the expressive power. We find that choosing the tensor rank r to be on the order of the bond dimension m, is sufficient to obtain high-accuracy groundstate approximations and to substantially outperform standard TTNS computations. Thus low-rank tensor networks are a promising route for the simulation of quantum matter and machine learning on large data sets.
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.