Membership in Moment Polytopes is in NP and coNP

DOI10.1137/15M1048859zbMATH Open1371.68105arXiv1511.03675OpenAlexW2254435734MaRDI QIDQ5269822FDOQ5269822

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

Publication date: 28 June 2017

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convexity properties of the moment mapping. III
• Quantum Computation and Quantum Information
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Convexity and Commuting Hamiltonians
• Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
• Computational Complexity
• Combinatorial Nullstellensatz
• Gelfand–Tsetlin Bases for Classical Lie Algebras
• Geometric complexity theory and tensor rank
• Classical Bruhat orders and lexicographic shellability
• An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
• The Pauli principle revisited
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information
• On convexity, the Weyl group and the Iwasawa decomposition
• A basis for representations of symplectic Lie algebras
• A Stratification of the Null Cone Via the Moment Map
• Nonzero Kronecker coefficients and what they tell us about spectra
• Polynomial bounds for rings of invariants
• Geometric invariant theory and generalized eigenvalue problem. II
• Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion
• The spectra of quantum states and the Kronecker coefficients of the symmetric group
• Honeycombs and sums of Hermitian matrices.
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Quantum state transformations and the Schubert calculus
• Eigenvalue distributions of reduced density matrices
• Deciding Positivity of Littlewood--Richardson Coefficients
• On vanishing of Kronecker coefficients
• Lie Groups, Lie Algebras, and Representations
• Inequalities for moment cones of finite-dimensional representations

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)