Universal points in the asymptotic spectrum of tensors
Universal points in the asymptotic spectrum of tensors
复制标题
张量渐进谱中的通用点
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Jeroen Zuiddam
中科院分区：
文献类型：
--
作者：
M. Christandl;Péter Vrana;Jeroen Zuiddam
对张量S和t的渐近限制问题是找到最小的β≥0，使得当n变到无穷大时，t的n次张量次方可以从S的(βn+o(N))次张量次方通过对张量腿应用线性映射而得到--这称为限制.应用包括计算代数复杂性理论中矩阵乘法的算术复杂性，通过随机局域运算确定纯量子态与量子信息论中经典通信之间渐近变换的可行性，在代数性质测试中确定某些性质的查询复杂性的界，以及在加法组合学中限定三色和自由集等组合结构的大小。自然，渐近限制问题需要障碍(考虑计算复杂性的下限)和构造(考虑快速矩阵乘法算法)。Strassen指出，对于障碍，只需考虑从k张量到非负实数的映射就足够了，这些映射在限制下是单调的，在对角张量上是规格化的，在直和下是可加的，在张量积下是可乘的，称为谱点(SFCS 1986和J.Reine Angew)。数学课。(1988年)。Strassen引入了支撑泛函，它是斜张量的谱点，是所有张量的严格子族(J.Reine Angew)。数学课。1991年)。在构造方面，一项重要的工作是紧张量和紧集的Coppersmith-Winograd方法。我们给出了所有复张量族的第一个非平凡谱点，称为量子泛函。寻找这样的万能谱点，三十年来一直是一个悬而未决的问题。我们使用了量子信息论、不变量理论和矩多面体的技术。我们给出了支撑泛函和我们的量子泛函之间的比较，并计算了通用值。本着Blasiak等人的精神，我们从几何不变量理论出发，将泛函与不稳定性联系起来。(分立肛门。2017年)。我们证明了量子泛函是关于片阶和多片阶的渐近上界，推广了Tao和Sawin的一个结果。此外，我们通过组合退化扩展了Coppersmith-Winograd方法，从而在渐近限制问题的组合形式的构造方面取得了进展。正则方法构造任意紧集的幂的大的自由对角线。我们的扩展版本适用于任何组合退化为紧集的集合。这推广了Kleinberg，Sawin和Speyer的一个结果。作为一个应用，我们通过将这个问题归结为Strassen关于约化多项式乘法的结果，在事后证明了最近关于三色和自由集的结果。本文的完整版本中有校样，可在https://arxiv.org/abs/1709.07851.上找到
The asymptotic restriction problem for tensors s and t is to find the smallest β ≥ 0 such that the nth tensor power of t can be obtained from the (β n+o(n))th tensor power of s by applying linear maps to the tensor legs — this is called restriction — when n goes to infinity. Applications include computing the arithmetic complexity of matrix multiplication in algebraic complexity theory, deciding the feasibility of an asymptotic transformation between pure quantum states via stochastic local operations and classical communication in quantum information theory, bounding the query complexity of certain properties in algebraic property testing, and bounding the size of combinatorial structures like tri-colored sum-free sets in additive combinatorics. Naturally, the asymptotic restriction problem asks for obstructions (think of lower bounds in computational complexity) and constructions (think of fast matrix multiplication algorithms). Strassen showed that for obstructions it is sufficient to consider maps from k-tensors to nonnegative reals, that are monotone under restriction, normalised on diagonal tensors, additive under direct sum and multiplicative under tensor product, named spectral points (SFCS 1986 and J. Reine Angew. Math. 1988). Strassen introduced the support functionals, which are spectral points for oblique tensors, a strict subfamily of all tensors (J. Reine Angew. Math. 1991). On the construction side, an important work is the Coppersmith-Winograd method for tight tensors and tight sets. We present the first nontrivial spectral points for the family of all complex tensors, named quantum functionals. Finding such universal spectral points has been an open problem for thirty years. We use techniques from quantum information theory, invariant theory and moment polytopes. We present comparisons among the support functionals and our quantum functionals, and compute generic values. We relate the functionals to instability from geometric invariant theory, in the spirit of Blasiak et al. (Discrete Anal. 2017). We prove that the quantum functionals are asymptotic upper bounds on slice-rank and multi-slice rank, extending a result of Tao and Sawin. Furthermore, we make progress on the construction side of the combinatorial version of the asymptotic restriction problem by extending the Coppersmith–Winograd method via combinatorial degeneration. The regular method constructs large free diagonals in powers of any tight set. Our extended version works for any set that has a combinatorial degeneration to a tight set. This generalizes a result of Kleinberg, Sawin and Speyer. As an application we reprove in hindsight recent results on tri-colored sum-free sets by reducing this problem to a result of Strassen on reduced polynomial multiplication. Proofs are in the full version of this paper, available at https://arxiv.org/abs/1709.07851.