Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond

Abstract

We study the problem of finding elements in the intersection of an arbitrary conic variety in ${\mathbb{F}}^n$ with a given linear subspace (where $\mathbb{F}$ can be the real or complex field). This problem captures a rich family of algorithmic problems under different choices of the variety. The special case of the variety consisting of rank-1 matrices already has strong connections to central problems in different areas like quantum information theory and tensor decompositions. This problem is known to be NP-hard in the worst case, even for the variety of rank-1 matrices. Surprisingly, despite these hardness results we develop an algorithm that solves this problem efficiently for "typical" subspaces. Here, the subspace $U\subseteq {\mathbb{F}}^n$ is chosen generically of a certain dimension, potentially with some generic elements of the variety contained in it. Our main result is a guarantee that our algorithm recovers all the elements of $U$ that lie in the variety, under some mild non-degeneracy assumptions on the variety. As corollaries, we obtain the following new results: $\bullet$ Polynomial time algorithms for several entangled subspaces problems in quantum entanglement, including determining r-entanglement, complete entanglement, and genuine entanglement of a subspace. While all of these problems are NP-hard in the worst case, our algorithm solves them in polynomial time for generic subspaces of dimension up to a constant multiple of the maximum possible. $\bullet$ Uniqueness results and polynomial time algorithmic guarantees for generic instances of a broad class of low-rank decomposition problems that go beyond tensor decompositions. Here, we recover a decomposition of the form ${\sum }_{i=1}^R{v}_i\otimes w_i$, where the $v_i$ are elements of the variety $X$. This implies new uniqueness results and genericity guarantees even in the special case of tensor decompositions.

arXiv comment39 pages. V3: Simplified some arguments and notation. Comments welcome!

References in corpus (25)

• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Separability criterion and inseparable mixed states with positive partial transposition
• Unextendible Product Bases and Bound Entanglement
• Unextendible Product Bases, Uncompletable Product Bases and Bound Entanglement
• Entanglement witnesses: construction, analysis and classification
• On the dimension of subspaces with bounded Schmidt rank
• On cap sets and the group-theoretic approach to matrix multiplication
• The Entanglement of Superpositions
• A completely entangled subspace of maximal dimension
• Quantum Codes of Maximal Distance and Highly Entangled Subspaces
• Upper bounds for sunflower-free sets
• A note on the optimality of decomposable entanglement witnesses and completely entangled subspaces
• The Growth Rate of Tri-Colored Sum-Free Sets
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
• Entanglement of Subspaces and Error Correcting Codes
• Spectral Learning on Matrices and Tensors
• Generic uniqueness of a structured matrix factorization and applications in blind source separation
• Entanglement of subspaces in terms of entanglement of superpositions
• Simple sufficient condition for subspace to be completely or genuinely entangled
• Multi-partite separable states with unique decompositions and construction of three qubit entanglement with positive partial transpose
• A Complete Hierarchy of Linear Systems for Certifying Quantum Entanglement of Subspaces
• Combinatorial results implied by many zero divisors in a group ring
• Overcomplete order-3 tensor decomposition, blind deconvolution and Gaussian mixture models