×

Membership in moment polytopes is in NP and coNP. (English) Zbl 1371.68105

Summary: We show that the problem of deciding membership in the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group is in NP and coNP. This is the first nontrivial result on the computational complexity of this problem, which naively amounts to a quadratically constrained program. Our result applies in particular to the Kronecker polytopes, and therefore to the problem of deciding positivity of the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard, in general [C. Ikenmeyer et al., “On vanishing of Kronecker coefficients”, Preprint, arXiv:1507.02955]. We discuss the consequences of our work in the context of complexity theory and the quantum marginal problem.

MSC:

68Q25 Analysis of algorithms and problem complexity
17B10 Representations of Lie algebras and Lie superalgebras, algebraic theory (weights)
52B55 Computational aspects related to convexity
53D20 Momentum maps; symplectic reduction
81R05 Finite-dimensional groups and algebras motivated by physics and their representations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon, {\it Combinatorial Nullstellensatz}, Combin. Probab. Comput., 8 (1999), pp. 7-29.
[2] M. Altunbulak and A. Klyachko, {\it The Pauli principle revisited}, Comm. Math. Phys., 282 (2008), pp. 287-322, . · Zbl 1159.81031
[3] M. F. Atiyah, {\it Convexity and commuting Hamiltonians}, Bull. Lond. Math. Soc., 14 (1982), pp. 1-15. 1981, . · Zbl 0482.58013
[4] A. Berenstein and R. Sjamaar, {\it Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion}, J. Amer. Math. Soc., 13 (2000), pp. 433-466, . · Zbl 0979.53092
[5] R. Bhatia, {\it Matrix Analysis}, Grad. Texts in Math 169, Springer New York, 1997, 2013, .
[6] J. Blasiak, K. Mulmuley, and M. Sohoni, {\it Geometric complexity theory {\it III}: On deciding nonvanishing of a Littlewood-Richardson coefficient}, J. Algebraic Combin., 36 (2012), pp. 103-110, . · Zbl 1271.03055
[7] P. Bürgisser and C. Ikenmeyer, {\it Geometric complexity theory and tensor rank}, in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 509-518, . · Zbl 1288.68103
[8] P. Bürgisser and C. Ikenmeyer, {\it Deciding positivity of Littlewood-Richardson coefficients}, SIAM J. Discrete Math., 27 (2013), pp. 1639-1681, . · Zbl 1285.05172
[9] P. Bürgisser, J. M. Landsberg, L. Manivel, and J. Weyman, {\it An overview of mathematical issues arising in the geometric complexity theory approach to VP \(≠\) VNP}, SIAM J. Comput., 40 (2011), pp. 1179-1209, . · Zbl 1252.68134
[10] M. Christandl, B. Doran, S. Kousidis, and M. Walter, {\it Eigenvalue distributions of reduced density matrices}, Comm. Math. Phys., 332 (2014), pp. 1-52, . · Zbl 1304.81051
[11] M. Christandl, B. Doran, and M. Walter, {\it Computing multiplicities of Lie group representations}, in 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Piscataway, NJ, 2012, pp. 639-648, .
[12] M. Christandl, A. Harrow, and G. Mitchison, {\it On nonzero Kronecker coefficients and their consequences for spectra}, Comm. Math. Phys., 270 (2007), pp. 575-585, . · Zbl 1123.81029
[13] M. Christandl and G. Mitchison, {\it The spectra of quantum states and the Kronecker coefficients of the symmetric group}, Comm. Math. Phys., 261 (2006), pp. 789-797, . · Zbl 1109.81038
[14] S. Daftuar and P. Hayden, {\it Quantum state transformations and the Schubert calculus}, Ann. Phys., 315 (2005), pp. 80-122, . · Zbl 1112.81017
[15] H. Derksen, {\it Polynomial bounds for rings of invariants}, Proc. Amer. Math. Soc., 129 (2001), pp. 955-963, . · Zbl 0969.13003
[16] I. M. Gelfand and M. L. Tsetlin, {\it Finite dimensional representations of the group of unimodular matrices}, in I. M. Gelfand, Collected Papers, Vol. II, Springer, Berlin, 1988, pp. 653-656.
[17] I. M. Gelfand and M. L. Tsetlin, {\it Finite dimensional representations of the group of orthogonal matrices}, in I. M. Gelfand, Collected Papers, Vol. II, Springer, Berlin, 1988, pp. 657-661.
[18] O. Goldreich, {\it Computational Complexity: A Conceptual Perspective}, Cambridge University Press, Cambridge, 2008, . · Zbl 1154.68056
[19] V. Guillemin and S. Sternberg, {\it Symplectic Techniques in Physics}, Cambridge University Press, Cambridge, 1990. · Zbl 0734.58005
[20] B. C. Hall, {\it Lie Groups, Lie Algebras, and Representations: An Elementary Introduction}, Grad. Texts in Math. 222, Springer, Cham, Switzerland 2015, . · Zbl 1316.22001
[21] M. Hindry and J. H. Silverman, {\it Diophantine Geometry: An Introduction}, Grad. Texts in Math. 201, Springer, New York, 2000, . · Zbl 0948.11023
[22] A. Horn, {\it Doubly stochastic matrices and the diagonal of a rotation matrix}, Amer. J. Math., 76 (1954), pp. 620-630, . · Zbl 0055.24601
[23] C. Ikenmeyer, K. D. Mulmuley, and M. Walter, {\it On Vanishing of Kronecker Coefficients}, preprint, , 2015. · Zbl 1382.68093
[24] A. A. Kirillov, {\it An introduction to Lie groups and Lie algebras}, Cambridge Stud. Adv. Math. 113, Cambridge University Press, Cambridge, 2008, .
[25] F. Kirwan, {\it Convexity properties of the moment mapping, {\it III}}, Invent. Math., 77 (1984), pp. 547-552. · Zbl 0561.58016
[26] A. Klyachko, {\it Quantum Marginal Problem and Representations of the Symmetric Group}, preprint, , 2004.
[27] A. Knutson and T. Tao, {\it Honeycombs and sums of Hermitian matrices}, Notices Amer. Math. Soc., 48 (2001), pp. 175-186. · Zbl 1047.15006
[28] B. Kostant, {\it On convexity, the Weyl group and the Iwasawa decomposition}, in Ann. Sci. Éc. Norm. Supér., 6 (1973), pp. 413-455. · Zbl 0293.22019
[29] V. Lakshmibai, {\it Bases for quantum Demazure modules}, Algebrak Groups and Their Generalizations. II, in Proc. Sympos. Pure Math. 56, AMS, Providence, AI, 1994, pp. 149-168. · Zbl 0848.17020
[30] Y.-K. Liu, M. Christandl, and F. Verstraete, {\it Quantum computational complexity of the N-representability problem: QMA complete}, Phys. Rev. Lett., 98 (2007), 110503, .
[31] A. Molev, {\it A basis for representations of symplectic Lie algebras}, Commu. Math. Phys., 201 (1999), pp. 591-618, . · Zbl 0931.17005
[32] A. Molev, {\it Gelfand-Tsetlin bases for classical Lie algebras}, in Handbook of Algebra, Vol. 4, Elsevier, Amsterdam, 2006, pp. 109-170. · Zbl 1211.17009
[33] K. D. Mulmuley, {\it Geometric Complexity Theory {\it VI}: The Flip via Saturated and Positive Integer Programming in Representation Theory and Algebraic Geometry}, preprint, , 2007.
[34] K. D. Mulmuley and M. Sohoni, {\it Geometric complexity theory I: An approach to the P vs. NP and related problems}, SIAM J. Comput., 31 (2001), pp. 496-526, . · Zbl 0992.03048
[35] L. Ness and D. Mumford, {\it A stratification of the null cone via the moment map}, Amer. J. Math., (1984), pp. 1281-1329, . · Zbl 0604.14006
[36] M. A. Nielsen and I. L. Chuang, {\it Quantum Computation and Quantum Information}, Cambridge University Press, Cambridge, 2010, . · Zbl 1288.81001
[37] R. A. Proctor, {\it Classical Bruhat orders and lexicographic shellability}, J. Algebra, 77 (1982), pp. 104-126, . · Zbl 0486.06002
[38] N. Ressayre, {\it Geometric invariant theory and the generalized eigenvalue problem}, Invent. Math., 180 (2010), pp. 389-441, . · Zbl 1197.14051
[39] I. Schur, {\it Über eine Klasse von Mittelbildungen mit Anwendungen auf die Determinantentheorie}, Sitzungsber. Berl. Math. Ges., 22 (1923), pp. 9-20. · JFM 49.0054.01
[40] J. T. Schwartz, {\it Fast probabilistic algorithms for verification of polynomial identities}, Journal ACM, 27 (1980), pp. 701-717, . · Zbl 0452.68050
[41] M. Vergne and M. Walter, {\it Inequalities for moment cones of finite-dimensional representations}, J. Symplectic Geom., to appear. · Zbl 1390.53095
[42] M. Walter, {\it Multipartite Quantum States and their Marginals}, PhD thesis, ETH Zurich, Zurich, 2014, .
[43] M. Walter, B. Doran, D. Gross, and M. Christandl, {\it Entanglement polytopes: Multiparticle entanglement from single-particle information}, Science, 340 (2013), pp. 1205-1208, . · Zbl 1355.81041
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.