The Complexity of Contracting Planar Tensor Network
share
Tensor networks have been an important concept and technique in many research areas such as quantum computation and machine learning. We study the complexity of evaluating the value of a tensor network. This is also called contracting the tensor network. In this article, we focus on computing the value of a planar tensor network where every tensor specified at a vertex is a Boolean symmetric function. We design two planar gadgets to obtain a sub-exponential time algorithm. The key is to remove high degree vertices while essentially not changing the size of the tensor network. The algorithm runs in time (O(√(|V|))). Furthermore, we use a counting version of the Sparsification Lemma to prove a matching lower bound (Ω(√(|V|))) assuming #ETH holds.
READ FULL TEXT