Universal points in the asymptotic spectrum of tensors

Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen

doi:10.1090/jams/996

Universal points in the asymptotic spectrum of tensors
HTML articles powered by AMS MathViewer

by Matthias Christandl, Péter Vrana and Jeroen Zuiddam

J. Amer. Math. Soc. 36 (2023), 31-79

DOI: https://doi.org/10.1090/jams/996

Published electronically: November 23, 2021

HTML | PDF | Request permission

Abstract:

Motivated by the problem of constructing fast matrix multiplication algorithms, Strassen (FOCS 1986, Crelle 1987–1991) introduced and developed the theory of asymptotic spectra of tensors. For any sub-semiring $\mathcal {X}$ of tensors (under direct sum and tensor product), the duality theorem that is at the core of this theory characterizes basic asymptotic properties of the elements of $\mathcal {X}$ in terms of the asymptotic spectrum of $\mathcal {X}$, which is defined as the collection of semiring homomorphisms from $\mathcal {X}$ to the non-negative reals with a natural monotonicity property. The asymptotic properties characterized by this duality encompass fundamental problems in complexity theory, combinatorics and quantum information.

Universal spectral points are elements in the asymptotic spectrum of the semiring of all tensors. Finding all universal spectral points suffices to find the asymptotic spectrum of any sub-semiring. The construction of non-trivial universal spectral points has been an open problem for more than thirty years. We construct, for the first time, a family of non-trivial universal spectral points over the complex numbers, called quantum functionals. We moreover prove that the quantum functionals precisely characterise the asymptotic slice rank of complex tensors. Our construction, which relies on techniques from quantum information theory and representation theory, connects the asymptotic spectrum of tensors to the quantum marginal problem and entanglement polytopes.

References

A. Alder and V. Strassen, On the algorithmic complexity of associative algebras, Theoret. Comput. Sci. 15 (1981), no. 2, 201–211. MR 623595, DOI 10.1016/0304-3975(81)90070-0
Noga Alon, Amir Shpilka, and Christopher Umans, On sunflowers and matrix multiplication, Comput. Complexity 22 (2013), no. 2, 219–243. MR 3055780, DOI 10.1007/s00037-013-0060-1
Srinivasan Arunachalam, Péter Vrana, and Jeroen Zuiddam, The asymptotic induced matching number of hypergraphs: balanced binary strings, Electron. J. Combin. 27 (2020), no. 3, Paper No. 3.12, 30. MR 4245125, DOI 10.37236/9019
Eberhard Becker and Niels Schwartz, Zum Darstellungssatz von Kadison-Dubois, Arch. Math. (Basel) 40 (1983), no. 5, 421–428 (German). MR 707730, DOI 10.1007/BF01192806
Ingemar Bengtsson and Karol Życzkowski, Geometry of quantum states, Cambridge University Press, Cambridge, 2006. An introduction to quantum entanglement. MR 2230995, DOI 10.1017/CBO9780511535048
Charles H. Bennett, Sandu Popescu, Daniel Rohrlich, John A. Smolin, and Ashish V. Thapliyal, Exact and asymptotic measures of multipartite pure-state entanglement, Phys. Rev. A 63 (2000), no. 1, 012307.
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie, Testing linear-invariant non-linear properties: a short report, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 260-268.
Arnab Bhattacharyya and Ning Xie, Lower bounds for testing triangle-freeness in Boolean functions, Comput. Complexity 24 (2015), no. 1, 65–101. MR 3320302, DOI 10.1007/s00037-014-0092-1
Markus Bläser, A ${5\over 2}n^2$-lower bound for the multiplicative complexity of $n\times n$-matrix multiplication, STACS 2001 (Dresden), Lecture Notes in Comput. Sci., vol. 2010, Springer, Berlin, 2001, pp. 99–109. MR 1890782, DOI 10.1007/3-540-44693-1_{9}
Markus Bläser, Fast matrix multiplication, Graduate Surveys, no. 5, Theory of Computing Library, 2013.
Markus Bläser and Vladimir Lysikov, On degeneration of tensors and algebras, 41st International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 58, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 19, 11. MR 3578455
Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans, On cap sets and the group-theoretic approach to matrix multiplication, Discrete Anal. , posted on (2017), Paper No. 3, 27. MR 3631613, DOI 10.19086/da.1245
Armand Borel, Linear algebraic groups, 2nd ed., Graduate Texts in Mathematics, vol. 126, Springer-Verlag, New York, 1991. MR 1102012, DOI 10.1007/978-1-4612-0941-6
Michel Brion, Sur l’image de l’application moment, Séminaire d’algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986) Lecture Notes in Math., vol. 1296, Springer, Berlin, 1987, pp. 177–192 (French). MR 932055, DOI 10.1007/BFb0078526
Michel Brion, Lectures on the geometry of flag varieties, Topics in cohomological studies of algebraic varieties, Trends Math., Birkhäuser, Basel, 2005, pp. 33–85. MR 2143072, DOI 10.1007/3-7643-7342-3_{2}
Jim Bryan, Zinovy Reichstein, and Mark Van Raamsdonk, Existence of locally maximally entangled quantum states via geometric invariant theory, Ann. Henri Poincaré 19 (2018), no. 8, 2491–2511. MR 3830220, DOI 10.1007/s00023-018-0682-6
Peter Bürgisser, Degenerationsordnung und trägerfunktional bilinearer abbildungen, Ph.D. Thesis, Universität Konstanz, 1990, http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-20311.
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson, Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory, 9th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 94, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 24, 20. MR 3761760
Peter Bürgisser and Christian Ikenmeyer, Geometric complexity theory and tensor rank [extended abstract], STOC’11—Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 509–518. MR 2932001, DOI 10.1145/1993636.1993704
Matthias Christandl, Aram W. Harrow, and Graeme Mitchison, Nonzero Kronecker coefficients and what they tell us about spectra, Comm. Math. Phys. 270 (2007), no. 3, 575–585. MR 2276458, DOI 10.1007/s00220-006-0157-3
Matthias Christandl, Vladimir Lysikov, and Jeroen Zuiddam, Weighted slice rank and a minimax correspondence to Strassen’s spectra, 2020.
Matthias Christandl and Graeme Mitchison, The spectra of quantum states and the Kronecker coefficients of the symmetric group, Comm. Math. Phys. 261 (2006), no. 3, 789–797. MR 2197548, DOI 10.1007/s00220-005-1435-1
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam, Asymptotic tensor rank of graph tensors: beyond matrix multiplication, Comput. Complexity 28 (2019), no. 1, 57–111. MR 3924627, DOI 10.1007/s00037-018-0172-8
Henry Cohn, Ankit Garg, Eric Naslund, Rafael Oliveira, and William F. Sawin, Personal communication.
Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Christopher Umans, Group-theoretic algorithms for matrix multiplication, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), IEEE, 2005, pp. 379–388.
Henry Cohn and Christopher Umans, A group-theoretic approach to fast matrix multiplication, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), IEEE, 2003, pp. 438–449.
Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach, Progression-free sets in $\Bbb Z^n_4$ are exponentially small, Ann. of Math. (2) 185 (2017), no. 1, 331–337. MR 3583357, DOI 10.4007/annals.2017.185.1.7
W. Dür, G. Vidal, and J. I. Cirac, Three qubits can be entangled in two inequivalent ways, Phys. Rev. A (3) 62 (2000), no. 6, 062314, 12. MR 1804183, DOI 10.1103/PhysRevA.62.062314
Yves Edel, Extensions of generalized product caps, Des. Codes Cryptogr. 31 (2004), no. 1, 5–14. MR 2031694, DOI 10.1023/A:1027365901231
Jordan S. Ellenberg and Dion Gijswijt, On large subsets of $\Bbb F^n_q$ with no three-term arithmetic progression, Ann. of Math. (2) 185 (2017), no. 1, 339–343. MR 3583358, DOI 10.4007/annals.2017.185.1.8
Matthias Franz, Moment polytopes of projective $G$-varieties and tensor products of symmetric group representations, J. Lie Theory 12 (2002), no. 2, 539–549. MR 1923785
Hu Fu and Robert Kleinberg, Improved lower bounds for testing triangle-freeness in Boolean functions via fast matrix multiplication, Approximation, randomization, and combinatorial optimization, LIPIcs. Leibniz Int. Proc. Inform., vol. 28, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014, pp. 669–676. MR 3319023
Ishay Haviv and Ning Xie, Sunflowers and testing triangle-freeness of functions, ITCS’15—Proceedings of the 6th Innovations in Theoretical Computer Science, ACM, New York, 2015, pp. 357–366. MR 3419029, DOI 10.1145/2688073.2688084
Ishay Haviv and Ning Xie, Sunflowers and testing triangle-freeness of functions, Comput. Complexity 26 (2017), no. 2, 497–530. MR 3645905, DOI 10.1007/s00037-016-0138-7
Masahito Hayashi and Keiji Matsumoto, Quantum universal variable-length source coding, Phys. Rev. A (3) 66 (2002), no. 2, 022311, 13. MR 1955142, DOI 10.1103/PhysRevA.66.022311
Ryszard Horodecki, PawełHorodecki, MichałHorodecki, and Karol Horodecki, Quantum entanglement, Rev. Modern Phys. 81 (2009), no. 2, 865–942. MR 2515619, DOI 10.1103/RevModPhys.81.865
Tali Kaufman and Madhu Sudan, Algebraic property testing: the role of invariance, STOC’08, ACM, New York, 2008, pp. 403–412. MR 2582904, DOI 10.1145/1374376.1374434
M. Keyl and R. F. Werner, Estimating the spectrum of a density operator, Phys. Rev. A (3) 64 (2001), no. 5, 052311, 5. MR 1878924, DOI 10.1103/PhysRevA.64.052311
Robert Kleinberg, David E. Speyer, and Will Sawin, The growth of tri-colored sum-free sets, Discrete Anal. , posted on (2018), Paper No. 12, 10. MR 3827120, DOI 10.19086/da.3734
Alexander Klyachko, Coherent states, entanglement, and geometric invariant theory, arXiv (2002).
Hanspeter Kraft, Geometrische Methoden in der Invariantentheorie, Aspects of Mathematics, D1, Friedr. Vieweg & Sohn, Braunschweig, 1984 (German). MR 768181, DOI 10.1007/978-3-322-83813-1
J. M. Landsberg, Tensors: geometry and applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012. MR 2865915, DOI 10.1090/gsm/128
J. M. Landsberg, New lower bounds for the rank of matrix multiplication, SIAM J. Comput. 43 (2014), no. 1, 144–149. MR 3162411, DOI 10.1137/120880276
J. M. Landsberg, Geometry and complexity theory, Cambridge Studies in Advanced Mathematics, vol. 169, Cambridge University Press, Cambridge, 2017. MR 3729273, DOI 10.1017/9781108183192
François Le Gall, Powers of tensors and fast matrix multiplication, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296–303. MR 3239939, DOI 10.1145/2608628.2608664
Eric Naslund, The partition rank of a tensor and $k$-right corners in $\Bbb F_q^n$, J. Combin. Theory Ser. A 174 (2020), 105190, 25. MR 4078997, DOI 10.1016/j.jcta.2019.105190
Linda Ness, A stratification of the null cone via the moment map, Amer. J. Math. 106 (1984), no. 6, 1281–1329. With an appendix by David Mumford. MR 765581, DOI 10.2307/2374395
Tomohiro Ogawa and Hiroshi Nagaoka, A new proof of the channel coding theorem via hypothesis testing in quantum information theory, IEEE International Symposium on Information Theory, IEEE, 2002, p. 73.
Adam Sawicki, MichałOszmaniec, and Marek Kuś, Convexity of momentum map, Morse index, and quantum entanglement, Rev. Math. Phys. 26 (2014), no. 3, 1450004, 39. MR 3195184, DOI 10.1142/S0129055X14500044
Asaf Shapira, Green’s conjecture and testing linear-invariant properties, STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, ACM, New York, 2009, pp. 159–166. MR 2780061
Reyer Sjamaar, Convexity properties of the moment mapping re-examined, Adv. Math. 138 (1998), no. 1, 46–91. MR 1645052, DOI 10.1006/aima.1998.1739
A. V. Smirnov, Decomposition of symmetric powers of irreducible representations of semisimple Lie algebras, and the Brion polytope, Tr. Mosk. Mat. Obs. 65 (2004), 230–252 (Russian, with Russian summary); English transl., Trans. Moscow Math. Soc. (2004), 213–234. MR 2193441, DOI 10.1090/s0077-1554-04-00143-8
Andrew James Stothers, On the complexity of matrix multiplication, Ph.D. Thesis, University of Edinburgh, 2010, http://hdl.handle.net/1842/4734.
Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
V. Strassen, The asymptotic spectrum of tensors and the exponent of matrix multiplication, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS 1986) (Washington, DC, USA), IEEE Computer Society, 1986, pp. 49–54.
V. Strassen, Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math. 375/376 (1987), 406–443. MR 882307, DOI 10.1515/crll.1987.375-376.406
V. Strassen, The asymptotic spectrum of tensors, J. Reine Angew. Math. 384 (1988), 102–152. MR 929980, DOI 10.1515/crll.1988.384.102
V. Strassen, Degeneration and complexity of bilinear maps: some asymptotic spectra, J. Reine Angew. Math. 413 (1991), 127–180. MR 1089800, DOI 10.1515/crll.1991.413.127
V. Strassen, Algebra and complexity, First European Congress of Mathematics, Vol. II (Paris, 1992) Progr. Math., vol. 120, Birkhäuser, Basel, 1994, pp. 429–446. MR 1341854
Volker Strassen, Komplexität und Geometrie bilinearer Abbildungen, Jahresber. Deutsch. Math.-Verein. 107 (2005), no. 1, 3–31 (German, with English summary). MR 2138544
Terence Tao, Structure and randomness, American Mathematical Society, Providence, RI, 2008. Pages from year one of a mathematical blog. MR 2459552, DOI 10.1090/mbk/059
Terence Tao, A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, 2016, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.
Terence Tao and Will Sawin, Notes on the “slice rank” of tensors, 2016, https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/.
Verena Tobler, Spezialisierung und degeneration von tensoren, Ph.D. Thesis, Universität Konstanz, 1991, http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-20324.
Alexandre B. Tsybakov, Introduction to nonparametric estimation, Springer Series in Statistics, Springer, New York, 2009. Revised and extended from the 2004 French original; Translated by Vladimir Zaiats. MR 2724359, DOI 10.1007/b13794
F. Verstraete, J. Dehaene, B. De Moor, and H. Verschelde, Four qubits can be entangled in nine different ways, Phys. Rev. A (3) 65 (2002), no. 5, 052112, 5. MR 1910235, DOI 10.1103/PhysRevA.65.052112
Péter Vrana and Matthias Christandl, Asymptotic entanglement transformation between W and GHZ states, J. Math. Phys. 56 (2015), no. 2, 022204, 12. MR 3390878, DOI 10.1063/1.4908106
Michael Walter, Brent Doran, David Gross, and Matthias Christandl, Entanglement polytopes: multiparticle entanglement from single-particle information, Science 340 (2013), no. 6137, 1205–1208. MR 3087706, DOI 10.1126/science.1232957
Konstantin Wernli, Computing entanglement polytopes, 2013, Master Thesis, ETH Zürich, Switzerland.
Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056
Andreas Winter, Coding theorem and strong converse for quantum channels, IEEE Trans. Inform. Theory 45 (1999), no. 7, 2481–2485. MR 1725132, DOI 10.1109/18.796385
Jeroen Zuiddam, Algebraic complexity, asymptotic spectra and entanglement polytopes, Ph.D. Thesis, University of Amsterdam, 2018.