Membership in moment polytopes is in NP and coNP

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.

20 pages

References in corpus (8)

• N-representability is QMA-complete
• The Pauli principle revisited
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Quantum marginal problem and representations of the symmetric group
• Quantum state transformations and the Schubert calculus
• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• Multipartite Quantum States and their Marginals
• An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers

Cited by in corpus (13)

• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• A complete hierarchy for the pure state marginal problem in quantum mechanics
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Generalized Pauli constraints in small atoms
• Quantum marginals from pure doubly excited states
• Interior-point methods on manifolds: theory and applications
• Permanent versus determinant, obstructions, and Kronecker coefficients
• The Horn inequalities from a geometric point of view
• The co-Pieri rule for Kronecker coefficients
• Polynomial time algorithms in invariant theory for torus actions
• All Kronecker coefficients are reduced Kronecker coefficients
• Barriers for recent methods in geodesic optimization
• Refining ensemble $N$-representability of one-body density matrices from partial information