Spectral norm of a symmetric tensor and its computation

Friedland, Shmuel; Wang, Li

doi:10.1090/mcom/3525

Spectral norm of a symmetric tensor and its computation
HTML articles powered by AMS MathViewer

by Shmuel Friedland and Li Wang HTML | PDF

Math. Comp. 89 (2020), 2175-2215 Request permission

Abstract:

We show that the spectral norm of a $d$-mode real or complex symmetric tensor in $n$ variables can be computed by finding the fixed points of the corresponding polynomial map. For a generic complex symmetric tensor the number of fixed points is finite, and we give upper and lower bounds for the number of fixed points. For $n=2$ we show that these fixed points are the roots of a corresponding univariate polynomial of degree at most $(d-1)^2+1$, except certain cases, which are completely analyzed. In particular, for $n=2$ the spectral norm of $d$-symmetric tensor is polynomially computable in $d$ with a given relative precision. For a fixed $n>2$ we show that the spectral norm of a $d$-mode symmetric tensor is polynomially computable in $d$ with a given relative precision with respect to the Hilbert-Schmidt norm of the tensor. These results show that the geometric measure of entanglement of $d$-mode symmetric qunits on $\mathbb {C}^n$ are polynomially computable for a fixed $n$.

References

Scott Aaronson and Alex Arkhipov, The computational complexity of linear optics, Theory Comput. 9 (2013), 143–252. MR 3029555, DOI 10.4086/toc.2013.v009a004
Antonio Auffinger, Gérard Ben Arous, and Jiří Černý, Random matrices and complexity of spin glasses, Comm. Pure Appl. Math. 66 (2013), no. 2, 165–201. MR 2999295, DOI 10.1002/cpa.21422
M. Aulbach, D. Markham, and Mi. Murao, The maximally entangled symmetric state in terms of the geometric measure, New Journal of Physics, 12 (2010), 073025.
S. Banach, Uber homogene Polynome in $(L^2)$, Studia Math., 7 (1938), pp. 36–44.
Magali Bardet, Jean-Charles Faugère, and Bruno Salvy, On the complexity of the $F_5$ Gröbner basis algorithm, J. Symbolic Comput. 70 (2015), 49–70. MR 3320794, DOI 10.1016/j.jsc.2014.09.025
Daniel J. Bates, Jonathan D. Hauenstein, Andrew J Sommese, and Charles W. Wampler, Bertini: Software for Numerical Algebraic Geometry, available at bertini.nd.edu with permanent doi: dx.doi.org/10.7274/R0H41PB5.
J. S. Bell, On the Einstein Podolsky Rosen paradox, Phys. Phys. Fiz. 1 (1964), no. 3, 195–200. MR 3790629, DOI 10.1103/PhysicsPhysiqueFizika.1.195
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
Dustin Cartwright and Bernd Sturmfels, The number of eigenvalues of a tensor, Linear Algebra Appl. 438 (2013), no. 2, 942–952. MR 2996375, DOI 10.1016/j.laa.2011.05.040
Bilian Chen, Simai He, Zhening Li, and Shuzhong Zhang, Maximum block improvement and polynomial optimization, SIAM J. Optim. 22 (2012), no. 1, 87–107. MR 2902686, DOI 10.1137/110834524
L. Chen, E. Chitambar, R. Duan, Z. Ji, A. Winter, Tensor Rank and Stochastic Entanglement Catalysis for Multipartite Pure States, Phys. Rev. Lett. 105 (2010), 200501.
Lin Chen and Shmuel Friedland, The tensor rank of tensor product of two three-qubit W states is eight, Linear Algebra Appl. 543 (2018), 1–16. MR 3760756, DOI 10.1016/j.laa.2017.12.015
Lin Chen, Aimin Xu, and Huangjun Zhu, Computation of the geometric measure of entanglement for pure multiqubit states, Phys. Rev. A (3) 82 (2010), no. 3, 032301, 10. MR 2772000, DOI 10.1103/PhysRevA.82.032301
R. Cleve, D. Gottesman, and H.-K. Lo, How to share a quantum secret, Phys. Rev. Lett. 83 (1999), 648, arXiv:quant-ph/9901025.pdf
Michel Coste, Real algebraic sets, Arc spaces and additive invariants in real algebraic and analytic geometry, Panor. Synthèses, vol. 24, Soc. Math. France, Paris, 2007, pp. 1–32 (English, with English and French summaries). MR 2409684
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle, On the best rank-1 and rank-$(R_1,R_2,\cdots ,R_N)$ approximation of higher-order tensors, SIAM J. Matrix Anal. Appl. 21 (2000), no. 4, 1324–1342. MR 1780276, DOI 10.1137/S0895479898346995
H. Derksen, S. Friedland, L.-H. Lim, and L. Wang, Theoretical and computational aspects of entanglement, arXiv:1705.07160.
H. Derksen and V. Makam, Highly entangled tensors, arXiv:1803.09788.
R. H. Dicke, Coherence in Spontaneous Radiation Processes, Physical Review. 93 (1) (1954), 99–110.
Jean-Guillaume Dumas, Clément Pernet, and Zhendong Wan, Efficient computation of the characteristic polynomial, ISSAC’05, ACM, New York, 2005, pp. 140–147. MR 2280540, DOI 10.1145/1073884.1073905
A. Einstein, B. Podolsky, and N. Rosen N, Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?, Phys. Rev. 47, is. 10, (1935), 777–780.
J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (1993), no. 4, 329–344. MR 1263871, DOI 10.1006/jsco.1993.1051
William Feller, An introduction to probability theory and its applications. Vol. I, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1957. 2nd ed. MR 0088081
Shmuel Friedland, Inverse eigenvalue problems, Linear Algebra Appl. 17 (1977), no. 1, 15–51. MR 472861, DOI 10.1016/0024-3795(77)90039-8
Shmuel Friedland, Best rank one approximation of real symmetric tensors can be chosen symmetric, Front. Math. China 8 (2013), no. 1, 19–40. MR 3010470, DOI 10.1007/s11464-012-0262-x
Shmuel Friedland, Matrices—algebra, analysis and applications, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2016. MR 3467205
Shmuel Friedland and Todd Kemp, Most boson quantum states are almost maximally entangled, Proc. Amer. Math. Soc. 146 (2018), no. 12, 5035–5049. MR 3866844, DOI 10.1090/proc/13933
Shmuel Friedland and Lek-Heng Lim, Nuclear norm of higher-order tensors, Math. Comp. 87 (2018), no. 311, 1255–1281. MR 3766387, DOI 10.1090/mcom/3239
S. Friedland, V. Mehrmann, R. Pajarola, and S. K. Suter, On best rank one approximation of tensors, Numer. Linear Algebra Appl. 20 (2013), no. 6, 942–955. MR 3141886, DOI 10.1002/nla.1878
Shmuel Friedland and Giorgio Ottaviani, The number of singular vector tuples and uniqueness of best rank-one approximation of tensors, Found. Comput. Math. 14 (2014), no. 6, 1209–1242. MR 3273677, DOI 10.1007/s10208-014-9194-z
Shmuel Friedland and Venu Tammali, Low-rank approximation of tensors, Numerical algebra, matrix theory, differential-algebraic equations and control theory, Springer, Cham, 2015, pp. 377–411. MR 3380288
S. Friedland and L. Wang, Geometric measure of entanglement of symmetric d-qubits is polynomial-time computable, arXiv:1608.01354.
I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
D. Gross, S. T. Flammia, and J. Eisert, Most quantum states are too entangled to be useful as computational resources, Phys. Rev. Lett. 102 (2009), no. 19, 190501, 4. MR 2507883, DOI 10.1103/PhysRevLett.102.190501
Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, DOI 10.1016/0304-3975(83)90002-6
A. Higuchi and A. Sudbery, How entangled can two couples get?, Phys. Lett. A 273 (2000), no. 4, 213–217. MR 1781603, DOI 10.1016/S0375-9601(00)00480-1
Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP-hard, J. ACM 60 (2013), no. 6, Art. 45, 39. MR 3144915, DOI 10.1145/2512329
John Hamal Hubbard and Dierk Schleicher, Multicorns are not path connected, Frontiers in complex dynamics, Princeton Math. Ser., vol. 51, Princeton Univ. Press, Princeton, NJ, 2014, pp. 73–102. MR 3289907
Robert Hübener, Matthias Kleinmann, Tzu-Chieh Wei, Carlos González-Guillén, and Otfried Gühne, Geometric measure of entanglement for symmetric states, Phys. Rev. A (3) 80 (2009), no. 3, 032324, 5. MR 2608644, DOI 10.1103/PhysRevA.80.032324
E. Jung, M.-R. Hwang, H. Kim, M.-S. Kim, D. Park, J.-W. Son, and S. Tamaryan, Reduced state uniquely defines the Groverian measure of the original pure state, Phys. Rev. A 77, 062317 (2008).
Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
J. Kuczyński and H. Woźniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl. 13 (1992), no. 4, 1094–1122. MR 1182715, DOI 10.1137/0613066
Angelos Mantzaflaris, Éric Schost, and Elias Tsigaridas, Sparse rational univariate representation, ISSAC’17—Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2017, pp. 301–308. MR 3703700, DOI 10.1145/3087604.3087653
J. Martin, O. Giraud, P.A. Braun, D. Braun and T. Bastin, Multiqubit symmetric states with high geometric entanglement, Phys. Rev. A 81 (2010), 062347.
Teo Mora, Solving polynomial equation systems. I, Encyclopedia of Mathematics and its Applications, vol. 88, Cambridge University Press, Cambridge, 2003. The Kronecker-Duval philosophy. MR 1966700, DOI 10.1017/CBO9780511542831
T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian J. Math. 17 (1965), 533–540. MR 175813, DOI 10.4153/CJM-1965-053-6
C. Andrew Neff and John H. Reif, An efficient algorithm for the complex roots problem, J. Complexity 12 (1996), no. 2, 81–115. MR 1398320, DOI 10.1006/jcom.1996.0008
A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, Classical boson sampling algorithms with superior performance to near-term experiments, Nat. Phys. 13 (2017), 1153.
Jiawang Nie and Li Wang, Semidefinite relaxations for best rank-1 tensor approximations, SIAM J. Matrix Anal. Appl. 35 (2014), no. 3, 1155–1179. MR 3252812, DOI 10.1137/130935112
Renato, R. Security of Quantum Key Distiribution, arXiv:quant-ph/0512258 (2006).
Bruce Reznick, Sums of even powers of real linear forms, Mem. Amer. Math. Soc. 96 (1992), no. 463, viii+155. MR 1096187, DOI 10.1090/memo/0463
Fabrice Rouillier, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput. 9 (1999), no. 5, 433–461. MR 1697179, DOI 10.1007/s002000050114
E. Schr$\mathrm {\ddot {o}}$dinger, Discussion of probability relations between separated systems, Mathematical Proceedings of the Cambridge Philosophical Society, 31 is. 4, (1935), 555–563.
E. Schr$\mathrm {\ddot {o}}$dinger, Probability relations between separated systems, Mathematical Proceedings of the Cambridge Philosophical Society, 32, is. 3, (1936), 446–452.
J. J. Sylvester, On a remarkable discovery in the theory of canonical forms and of hyperdeterminants, Phil. Mag. 2 (1851), 391–410 (Collected papers, Vol. I, Paper 41).
Sayatnova Tamaryan, Tzu-Chieh Wei, and DaeKil Park, Maximally entangled three-qubit states via geometric measure of entanglement, Phys. Rev. A (3) 80 (2009), no. 5, 052315, 10. MR 2629520, DOI 10.1103/PhysRevA.80.052315
J.J. Thomson, On the Structure of the Atom: An Investigation of the Stability of the Periods of Oscillation of a number of Corpuscles arranged at equal intervals around the Circumference of a Circle with Application of the results to the Theory of Atomic Structure, Philosophical magazine, Series 6, Volume 7, Number 39, pp 237-265, March 1904.
L. L. Whyte, Unique arrangements of points on a sphere, Amer. Math. Monthly 59 (1952), 606–611. MR 50303, DOI 10.2307/2306764
Tong Zhang and Gene H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl. 23 (2001), no. 2, 534–550. MR 1871328, DOI 10.1137/S0895479899352045
B. L. van der Waerden, Modern Algebra. Vol. I, Frederick Ungar Publishing Co., New York, N. Y., 1949. Translated from the second revised German edition by Fred Blum; With revisions and additions by the author. MR 0029363