Tensor networks are nowadays the backbone of classical simulations of quantum many-body systems and quantum circuits. This stems from the fact that the simulation result can be obtained by contracting a corresponding tensor network. While tensor contraction itself is a rather simple operation, the order in which the tensors of the network are contracted significantly impacts the time and memory performance. For this reason, one aims at finding a priori an optimal contraction order under a cost function that models the execution time of the whole network contraction.

However, there is a caveat: the problem of finding the optimal contraction is NP-complete. As a consequence, most works either improve over the exponential algorithm or fall back to greedy approaches. We argue that this is a defeatist position and show that we can indeed find optimal contraction orders for a more restrictive class of tensor networks. Namely, we prove that tree tensor networks accept optimal linear contraction orders. The result comes from a fascinating yet non-trivial link between database join ordering and the presented problem. To this end, we adapt a decade-old algorithm to the context of tensor networks.

Beyond the optimality results, we explore several ad-hoc join ordering techniques to provide near-optimal contraction orders for arbitrary tensor networks.