Universal points in the asymptotic spectrum of tensors
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Universal points in the asymptotic spectrum of tensors. / Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen.
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. Association for Computing Machinery, 2018. p. 289-296.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Universal points in the asymptotic spectrum of tensors
AU - Christandl, Matthias
AU - Vrana, Péter
AU - Zuiddam, Jeroen
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Asymptotic restriction
KW - Asymptotic spectrum
KW - Cap set problem
KW - Classical communication (slocc)
KW - Entanglement monotones
KW - Fast matrix multiplication
KW - Moment polytope
KW - Quantum entropy
KW - Reduced polynomial multiplication
KW - Stochastic local operations
KW - Tensors
UR - http://www.scopus.com/inward/record.url?scp=85049884625&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188766
DO - 10.1145/3188745.3188766
M3 - Article in proceedings
AN - SCOPUS:85049884625
SP - 289
EP - 296
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Henzinger, Monika
A2 - Kempe, David
A2 - Diakonikolas, Ilias
PB - Association for Computing Machinery
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -
ID: 215040243