Asymptotic tensor rank of graph tensors: beyond matrix multiplication

Abstract

We present an upper bound on the exponent of the asymptotic behaviour of the tensor rank of a family of tensors defined by the complete graph on $k$ vertices. For $k\ge 4$, we show that the exponent per edge is at most 0.77, outperforming the best known upper bound on the exponent per edge for matrix multiplication ($k=3$), which is approximately 0.79. We raise the question whether for some $k$ the exponent per edge can be below $2/3$, i.e. can outperform matrix multiplication even if the matrix multiplication exponent equals 2. In order to obtain our results, we generalise to higher order tensors a result by Strassen on the asymptotic subrank of tight tensors and a result by Coppersmith and Winograd on the asymptotic rank of matrix multiplication. Our results have applications in entanglement theory and communication complexity.

References in corpus (3)

• Characterizing the entanglement of symmetric many-particle spin-1/2 systems
• Entanglement distillation from Greenberger-Horne-Zeilinger shares
• Tensor surgery and tensor rank

Cited by in corpus (9)

• Dimension of Tensor Network varieties
• A Gap in the Subrank of Tensors
• A family of multipartite entanglement measures
• Distillation of Greenberger-Horne-Zeilinger states by combinatorial methods
• Universal points in the asymptotic spectrum of tensors
• The resource theory of tensor networks
• Border rank non-additivity for higher order tensors
• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
• The Tensor as an Informational Resource