Computing moment polytopes of tensors, with applications in algebraic complexity and quantum information

Tensors play a central role in various areas of computer science and mathematics, such as algebraic complexity theory (matrix multiplication), quantum information theory (entanglement), and additive combinatorics (slice rank). Fundamental problems about tensors are strongly tied to well-known questions in computational complexity — such as the problem of determining the matrix multiplication exponent via asymptotic rank, and the stronger Strassen asymptotic rank conjecture, which has recently been intimately linked to a whole range of computational problems. Unlike matrices, which are often well understood through their rank, tensors have such intricate structure that understanding them (and aforementioned problems) requires information of a more subtle nature. The moment polytope, going back decades to work in symplectic geometry, invariant theory, and representation theory, is a mathematical object associated to any tensor that collects such "rank-like" information. Their relevance has become apparent in several areas: (1) through applications in geometric complexity theory (GCT), (2) in the construction of functions in Strassen’s asymptotic spectrum of tensors, (3) as entanglement polytopes in quantum information theory, and (4) in optimization via scaling algorithms. Despite their fundamental role and interest from many angles, little is known about these polytopes, and in particular for tensors beyond $\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^2$ and $\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^2$ only sporadically have they been computed. Even less is known about the polytopes' inclusions and separations (which are particularly relevant for applications). We give a new algorithm for computing moment polytopes of tensors (and in fact moment polytopes for a natural general class of reductive algebraic groups) based on a mathematical characterization of moment polytopes by Franz. This algorithm enables us to compute moment polytopes of tensors of dimension an order of magnitude larger than previous methods, allowing us to compute with certainty, for the first time, all moment polytopes of tensors in $\mathbb{C}^3\otimes\mathbb{C}^3\otimes\mathbb{C}^3$, and with high probability those in $\mathbb{C}^4\otimes\mathbb{C}^4\otimes\mathbb{C}^4$. Towards an open problem in geometric complexity theory, we prove (guided by moment polytopes computed with our algorithm) separations between the moment polytopes of matrix multiplication tensors and unit tensors, showing in particular that the matrix multiplication moment polytopes are not maximal (i.e., not equal to the corresponding Kronecker polytopes). As a consequence of the above, we obtain a no-go result for a certain operational characterization of moment polytope inclusion, by proving that Strassen's asymptotic restriction on tensors does not imply moment polytope inclusion. Finally, based on our algorithmic observations, we construct explicit (concise) non-free tensors in every format $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$, thus solving a "hay in a haystack" problem for this generic property that plays an important role in Strassen's theory of asymptotic spectra.

• View at Publisher

Free Full Text ( Final Version , 765kb )