Nearly tight bounds for testing tree tensor network states

Abstract

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 on $n$ qudits with bond dimension at most $r$, or is far in trace distance from any such state. We first establish that, independent of the dimension of the state, $O(nr^2)$ copies suffice to accomplish this task with one-sided error. We then prove that $Ω(n r^2/\log n)$ copies are necessary for any test with one-sided error whenever $r\geq 2 + \log n$. In particular, this closes a roughly quadratic gap in the previous bounds for testing matrix product states in this setting. On the other hand, when $r=2$ we show that $Θ(\sqrt{n})$ copies are both necessary and sufficient for the related task of testing whether a state is a product of $n$ bipartite states having Schmidt-rank at most $r$, 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 on $r+1$ copies of the state.