×

Spectral norm of a symmetric tensor and its computation. (English) Zbl 1452.15013

Summary: 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\).

MSC:

15A69 Multilinear algebra, tensor calculus
15A18 Eigenvalues, singular values, and eigenvectors
68W30 Symbolic computation and algebraic computation
81P40 Quantum coherence, entanglement, quantum correlations
13P15 Solving polynomial systems; resultants
65H04 Numerical computation of roots of polynomial equations

Software:

Bertini; ISOLATE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aaronson, Scott; Arkhipov, Alex, The computational complexity of linear optics, Theory Comput., 9, 143-252 (2013) · Zbl 1298.81046 · doi:10.4086/toc.2013.v009a004
[2] Auffinger, Antonio; Ben Arous, G\'{e}rard; Cern\'{y}, Ji\v{r}\'{\i}, Random matrices and complexity of spin glasses, Comm. Pure Appl. Math., 66, 2, 165-201 (2013) · Zbl 1269.82066 · doi:10.1002/cpa.21422
[3] AMM10 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. · Zbl 1445.81009
[4] Ban38 S. Banach, Uber homogene Polynome in \((L^2)\), Studia Math., 7 (1938), pp. 36-44. · Zbl 0018.21902
[5] Bardet, Magali; Faug\`ere, Jean-Charles; Salvy, Bruno, On the complexity of the \(F_5\) Gr\"{o}bner basis algorithm, J. Symbolic Comput., 70, 49-70 (2015) · Zbl 1328.68319 · doi:10.1016/j.jsc.2014.09.025
[6] BHSW06 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.
[7] Bell, J. S., On the Einstein Podolsky Rosen paradox, Phys. Phys. Fiz., 1, 3, 195-200 (1964) · doi:10.1103/PhysicsPhysiqueFizika.1.195
[8] Bengtsson, Ingemar; \.{Z}yczkowski, Karol, Geometry of quantum states, xii+466 pp. (2006), Cambridge University Press, Cambridge · Zbl 1155.81002 · doi:10.1017/CBO9780511535048
[9] Cartwright, Dustin; Sturmfels, Bernd, The number of eigenvalues of a tensor, Linear Algebra Appl., 438, 2, 942-952 (2013) · Zbl 1277.15007 · doi:10.1016/j.laa.2011.05.040
[10] Chen, Bilian; He, Simai; Li, Zhening; Zhang, Shuzhong, Maximum block improvement and polynomial optimization, SIAM J. Optim., 22, 1, 87-107 (2012) · Zbl 1250.90069 · doi:10.1137/110834524
[11] CCDWL. 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.
[12] Chen, Lin; Friedland, Shmuel, The tensor rank of tensor product of two three-qubit W states is eight, Linear Algebra Appl., 543, 1-16 (2018) · Zbl 1382.15037 · doi:10.1016/j.laa.2017.12.015
[13] Chen, Lin; Xu, Aimin; Zhu, Huangjun, Computation of the geometric measure of entanglement for pure multiqubit states, Phys. Rev. A (3), 82, 3, 032301, 10 pp. (2010) · Zbl 1255.81056 · doi:10.1103/PhysRevA.82.032301
[14] CGL99 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
[15] Coste, Michel, Real algebraic sets. Arc spaces and additive invariants in real algebraic and analytic geometry, Panor. Synth\`eses 24, 1-32 (2007), Soc. Math. France, Paris · Zbl 1144.14305
[16] De Lathauwer, Lieven; De Moor, Bart; Vandewalle, Joos, 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, 4, 1324-1342 (2000) · Zbl 0958.15026 · doi:10.1137/S0895479898346995
[17] DFLW17 H. Derksen, S. Friedland, L.-H. Lim, and L. Wang, Theoretical and computational aspects of entanglement, arXiv:1705.07160.
[18] DM18 H. Derksen and V. Makam, Highly entangled tensors, arXiv:1803.09788.
[19] Dic R. H. Dicke, Coherence in Spontaneous Radiation Processes, Physical Review. 93 (1) (1954), 99-110. · Zbl 0055.21702
[20] Dumas, Jean-Guillaume; Pernet, Cl\'{e}ment; Wan, Zhendong, Efficient computation of the characteristic polynomial. ISSAC’05, 140-147 (2005), ACM, New York · Zbl 1360.65123 · doi:10.1145/1073884.1073905
[21] EPR35 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. · Zbl 0012.04201
[22] Faug\`ere, J. C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gr\"{o}bner bases by change of ordering, J. Symbolic Comput., 16, 4, 329-344 (1993) · Zbl 0805.13007 · doi:10.1006/jsco.1993.1051
[23] Feller, William, An Introduction to Probability Theory and Its Applications. Vol. I, xv+461 pp. (1957), John Wiley and Sons, Inc., New York; Chapman and Hall, Ltd., London · Zbl 0077.12201
[24] Friedland, Shmuel, Inverse eigenvalue problems, Linear Algebra Appl., 17, 1, 15-51 (1977) · Zbl 0358.15007 · doi:10.1016/0024-3795(77)90039-8
[25] Friedland, Shmuel, Best rank one approximation of real symmetric tensors can be chosen symmetric, Front. Math. China, 8, 1, 19-40 (2013) · Zbl 1264.15026 · doi:10.1007/s11464-012-0262-x
[26] Friedland, Shmuel, Matrices-Algebra, Analysis and Applications, xii+582 pp. (2016), World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ · Zbl 1337.15002
[27] Friedland, Shmuel; Kemp, Todd, Most boson quantum states are almost maximally entangled, Proc. Amer. Math. Soc., 146, 12, 5035-5049 (2018) · Zbl 1406.81012 · doi:10.1090/proc/13933
[28] Friedland, Shmuel; Lim, Lek-Heng, Nuclear norm of higher-order tensors, Math. Comp., 87, 311, 1255-1281 (2018) · Zbl 1383.15018 · doi:10.1090/mcom/3239
[29] Friedland, S.; Mehrmann, V.; Pajarola, R.; Suter, S. K., On best rank one approximation of tensors, Numer. Linear Algebra Appl., 20, 6, 942-955 (2013) · Zbl 1313.65085 · doi:10.1002/nla.1878
[30] Friedland, Shmuel; Ottaviani, Giorgio, The number of singular vector tuples and uniqueness of best rank-one approximation of tensors, Found. Comput. Math., 14, 6, 1209-1242 (2014) · Zbl 1326.15036 · doi:10.1007/s10208-014-9194-z
[31] Friedland, Shmuel; Tammali, Venu, Low-rank approximation of tensors. Numerical algebra, matrix theory, differential-algebraic equations and control theory, 377-411 (2015), Springer, Cham · Zbl 1327.65080
[32] FW16 S. Friedland and L. Wang, Geometric measure of entanglement of symmetric d-qubits is polynomial-time computable, arXiv:1608.01354.
[33] Gel\cprime fand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications, x+523 pp. (1994), Birkh\"{a}user Boston, Inc., Boston, MA · Zbl 0827.14036 · doi:10.1007/978-0-8176-4771-1
[34] Golub, Gene H.; Van Loan, Charles F., Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, xiv+756 pp. (2013), Johns Hopkins University Press, Baltimore, MD · Zbl 1268.65037
[35] Gross, D.; Flammia, S. T.; Eisert, J., Most quantum states are too entangled to be useful as computational resources, Phys. Rev. Lett., 102, 19, 190501, 4 pp. (2009) · doi:10.1103/PhysRevLett.102.190501
[36] Heintz, Joos, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 3, 239-277 (1983) · Zbl 0546.03017 · doi:10.1016/0304-3975(83)90002-6
[37] Higuchi, A.; Sudbery, A., How entangled can two couples get?, Phys. Lett. A, 273, 4, 213-217 (2000) · Zbl 1059.81511 · doi:10.1016/S0375-9601(00)00480-1
[38] Hillar, Christopher J.; Lim, Lek-Heng, Most tensor problems are NP-hard, J. ACM, 60, 6, Art. 45, 39 pp. (2013) · Zbl 1281.68126 · doi:10.1145/2512329
[39] Hubbard, John Hamal; Schleicher, Dierk, Multicorns are not path connected. Frontiers in complex dynamics, Princeton Math. Ser. 51, 73-102 (2014), Princeton Univ. Press, Princeton, NJ · Zbl 1355.37070
[40] H\"{u}bener, Robert; Kleinmann, Matthias; Wei, Tzu-Chieh; Gonz\'{a}lez-Guill\'{e}n, Carlos; G\"{u}hne, Otfried, Geometric measure of entanglement for symmetric states, Phys. Rev. A (3), 80, 3, 032324, 5 pp. (2009) · doi:10.1103/PhysRevA.80.032324
[41] Jungetall08 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).
[42] Karp, Richard M., Reducibility among combinatorial problems. Complexity of computer computations, Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972, 85-103 (1972), Plenum, New York · Zbl 1467.68065
[43] Kuczy\'{n}ski, J.; Wo\'{z}niakowski, H., Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., 13, 4, 1094-1122 (1992) · Zbl 0759.65016 · doi:10.1137/0613066
[44] Mantzaflaris, Angelos; Schost, \'{E}ric; Tsigaridas, Elias, Sparse rational univariate representation. ISSAC’17-Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, 301-308 (2017), ACM, New York · Zbl 1458.68285
[45] MGBB10 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.
[46] Mora, Teo, Solving Polynomial Equation Systems. I, Encyclopedia of Mathematics and its Applications 88, xiv+423 pp. (2003), Cambridge University Press, Cambridge · Zbl 1059.12001 · doi:10.1017/CBO9780511542831
[47] Motzkin, T. S.; Straus, E. G., Maxima for graphs and a new proof of a theorem of Tur\'{a}n, Canadian J. Math., 17, 533-540 (1965) · Zbl 0129.39902 · doi:10.4153/CJM-1965-053-6
[48] Neff, C. Andrew; Reif, John H., An efficient algorithm for the complex roots problem, J. Complexity, 12, 2, 81-115 (1996) · Zbl 0888.12005 · doi:10.1006/jcom.1996.0008
[49] Netall 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.
[50] Nie, Jiawang; Wang, Li, Semidefinite relaxations for best rank-1 tensor approximations, SIAM J. Matrix Anal. Appl., 35, 3, 1155-1179 (2014) · Zbl 1305.65134 · doi:10.1137/130935112
[51] Ren05 Renato, R. Security of Quantum Key Distiribution, arXiv:quant-ph/0512258 (2006).
[52] Reznick, Bruce, Sums of even powers of real linear forms, Mem. Amer. Math. Soc., 96, 463, viii+155 pp. (1992) · Zbl 0762.11019 · doi:10.1090/memo/0463
[53] Rouillier, Fabrice, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008 · doi:10.1007/s002000050114
[54] Sch35 E. Schr \(\ddoto\) dinger, Discussion of probability relations between separated systems, Mathematical Proceedings of the Cambridge Philosophical Society, 31 is. 4, (1935), 555-563. · JFM 61.1561.03
[55] Sch36 E. Schr \(\ddoto\) dinger, Probability relations between separated systems, Mathematical Proceedings of the Cambridge Philosophical Society, 32, is. 3, (1936), 446-452. · Zbl 0015.04403
[56] Syl51 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).
[57] Tamaryan, Sayatnova; Wei, Tzu-Chieh; Park, DaeKil, Maximally entangled three-qubit states via geometric measure of entanglement, Phys. Rev. A (3), 80, 5, 052315, 10 pp. (2009) · doi:10.1103/PhysRevA.80.052315
[58] Tho04 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. · JFM 35.0790.01
[59] Whyte, L. L., Unique arrangements of points on a sphere, Amer. Math. Monthly, 59, 606-611 (1952) · Zbl 0048.13602 · doi:10.2307/2306764
[60] Zhang, Tong; Golub, Gene H., Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl., 23, 2, 534-550 (2001) · Zbl 1001.65036 · doi:10.1137/S0895479899352045
[61] van der Waerden, B. L., Modern Algebra. Vol. I, xii+264 pp. (1949), Frederick Ungar Publishing Co., New York, N. Y. · Zbl 0039.00902
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.