Membership in moment polytopes is in NP and coNP

DOI10.1137/15M1048859zbMATH Open1371.68105OpenAlexW2254435734MaRDI QIDQ5269822FDOQ5269822

Authors Peter Bürgisser, Matthias Christandl, Michael Walter, Ketan D. Mulmuley

Publication date 28 June 2017

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03675

zbMATH Keywords

computational complexityquantum information theoryKronecker coefficientsasymptotic representation theorymoment polytopequantum marginal problem

Mathematics Subject Classification ID

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

Abstract: 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 non-trivial 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 [Ikenmeyer, Mulmuley and Walter, arXiv:1507.02955]. We discuss the consequences of our work in the context of complexity theory and the quantum marginal problem.

Recommendations

• On the computational complexity of membership problems for the completely positive cone and its dual
• On vanishing of Kronecker coefficients
• On the complexity of computing Kronecker coefficients
• The computational complexity of plethysm coefficients
• The complexity of computing Kronecker coefficients

Cites work

• scientific article; zbMATH DE number 50101 (Why is no real title available?)
• scientific article; zbMATH DE number 647415 (Why is no real title available?)
• scientific article; zbMATH DE number 1466163 (Why is no real title available?)
• A Stratification of the Null Cone Via the Moment Map
• A basis for representations of symplectic Lie algebras
• An introduction to Lie groups and Lie algebras
• An overview of mathematical issues arising in the geometric complexity theory approach to \(\mathbf{VP}\neq\mathbf{VNP}\)
• Classical Bruhat orders and lexicographic shellability
• Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion
• Combinatorial Nullstellensatz
• Computational Complexity
• Convexity and Commuting Hamiltonians
• Convexity properties of the moment mapping. III
• Deciding positivity of Littlewood-Richardson coefficients
• Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
• Eigenvalue distributions of reduced density matrices
• Entanglement polytopes: multiparticle entanglement from single-particle information
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Gelfand-Tsetlin bases for classical Lie algebras
• Geometric complexity theory and tensor rank
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Honeycombs and sums of Hermitian matrices.
• Inequalities for moment cones of finite-dimensional representations
• Lie Groups, Lie Algebras, and Representations
• Nonzero Kronecker coefficients and what they tell us about spectra
• On convexity, the Weyl group and the Iwasawa decomposition
• On vanishing of Kronecker coefficients
• Polynomial bounds for rings of invariants
• Quantum computation and quantum information. 10th anniversary edition
• Quantum state transformations and the Schubert calculus
• The Pauli principle revisited
• The spectra of quantum states and the Kronecker coefficients of the symmetric group

Cited in

(5)

• The Horn inequalities from a geometric point of view
• On vanishing of Kronecker coefficients
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• All Kronecker coefficients are reduced Kronecker coefficients
• Quantum marginals from pure doubly excited states

This page was built for publication: Membership in moment polytopes is in NP and coNP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5269822)