On the Optimal Linear Contraction Order for Tree Tensor Networks

Tensor networks are nowadays the backbone of classical simulations of quantum many-body systems and quantum circuits. Most tensor methods rely on the fact that we can eventually contract the tensor network to obtain the final result. While the contraction operation itself is trivial, its execution time is highly dependent on the order in which the contractions are performed. To this end, one tries to find beforehand an optimal order in which the contractions should be performed. However, there is a drawback: the general problem of finding the optimal contraction order is NP-complete. Therefore, one must settle for a mixture of exponential algorithms for small problems, e.g., $n \leq 20$, and otherwise hope for good contraction orders. For this reason, previous research has focused on the latter part, trying to find better heuristics. In this work, we take a more conservative approach and show that tree tensor networks accept optimal linear contraction orders. Beyond the optimality results, we adapt two join ordering techniques that can build on our work to guarantee near-optimal orders for arbitrary tensor networks.