Efficient algorithms for tensor scaling, quantum marginals and moment polytopes

Abstract

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

References in corpus (29)

• Three qubits can be entangled in two inequivalent ways
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Exact and Asymptotic Measures of Multipartite Pure State Entanglement
• Normal forms and entanglement measures for multipartite quantum states
• Quantum marginal problem and N-representability
• Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information
• 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
• One-qubit reduced states of a pure many-qubit state: polygon inequalities
• On Nonzero Kronecker Coefficients and their Consequences for Spectra
• On vanishing of Kronecker coefficients
• Geometric Invariant Theory and Generalized Eigenvalue Problem
• Geometric Invariant Theory and Generalized Eigenvalue Problem II
• Quantum state transformations and the Schubert calculus
• Convexity of momentum map, Morse index, and quantum entanglement
• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Combinatorial and algorithmic aspects of hyperbolic polynomials
• An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP
• Inequalities for Moment Cones of Finite-Dimensional Representations
• Multipartite Quantum States and their Marginals
• Membership in moment polytopes is in NP and coNP
• Geometric Complexity Theory and Tensor Rank
• Constructive noncommutative rank computation is in deterministic polynomial time
• Explicit Lower Bounds via Geometric Complexity Theory
• Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion

Cited by in corpus (20)

• 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
• Convex optimization using quantum oracles
• Fixed-Depth Two-Qubit Circuits and the Monodromy Polytope
• The minimal canonical form of a tensor network
• Quantum Brascamp-Lieb Dualities
• Interior-point methods on manifolds: theory and applications
• Rigorous Guarantees for Tyler's M-estimator via quantum expansion
• Duistermaat-Heckman measure and the mixture of quantum states
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• Polynomial time algorithms in invariant theory for torus actions
• On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups
• Capacity Lower Bounds via Productization
• Refuting spectral compatibility of quantum marginals
• Barriers for recent methods in geodesic optimization
• Quantum algorithms for matrix scaling and matrix balancing
• Generalized Pauli constraints in large systems: the Pauli principle dominates
• General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography