Exponential time complexity for contracting tensor networks

Abstract This article establishes a unified complexity framework for tensor network contraction—a fundamental counting problem. Since the computational complexity crucially depends on the underlying graph’s separator properties, we develop edge separator theorems for finite element graphs and $H$-minor-free graphs (excluding any simple graph $H$ as a minor), and present sub-exponential contraction algorithms for these graph classes. These algorithms, along with the algorithm for contraction on planar graphs are further accelerated by transforming each high-dimensional tensor into a series of low-dimensional tensors. Two methods are involved in this process respectively—the “adder” gadget that can equivalently represent any Boolean symmetric tensor, and the CANDECOMP/PARAFAC decomposition that can express any tensor as vector product sums. In particular, we prove corresponding lower bounds under #ETH, establishing near-optimality of our algorithms. Also, we present a treewidth-parameterized contraction algorithm, and therefore develop a fine-grained dichotomy for tensor network contraction, contingent on the Hadwiger number.