The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.
The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.
We determine the border subrank of higher order structure tensors of several families of algebras, and in particular obtain the following results. (1) We determine tight bounds on the border subrank of k-fold matrix multiplication and k-fold upper triangular matrix multiplication for all k. (2) We determine the border subrank of the higher order structure tensors of truncated polynomial algebras, null algebras, and apolar algebras of a quadric. (3) We determine the border subrank of the higher order structure tensors of the Lie algebra sl2 for all orders. (4) We prove that degeneration of structure tensors of algebras propagates from higher to lower order. Along the way, we investigate which upper bound methods (geometric rank, G-stable rank, socle degree) are effective in which settings, and how they relate. Our work extends the results of Strassen (J.~Reine Angew.~Math., 1987, 1991), who determined the asymptotic subrank of these algebras for tensors of order three, in two directions: we determine the border subrank itself rather than its asymptotic version, and we consider higher order structure tensors.
It is well known that tensor decompositions show separations, that is, constraints on local terms (such as positivity) may entail an arbitrarily high cost in their representation. Here, we show that many of these separations disappear in the approximate case. Specifically, for every approximation error ɛ and norm, we define the approximate rank as the minimum rank of an element in the ɛ-ball with respect to that norm. For positive semidefinite matrices, we show that the separations between rank, purification rank, and separable rank disappear for a large class of Schatten p-norms. For non-negative tensors, we show that the separations between rank, positive semidefinite rank, and non-negative rank disappear for all ℓp-norms with p > 1. For the trace norm (p = 1), we obtain upper bounds that depend on the ambient dimension. We also provide a deterministic algorithm to obtain the approximate decomposition attaining our bounds. Our main tool is an approximate version of the Carathéodory theorem. Our results imply that many separations are not robust under small perturbations of the tensor, with implications in quantum many-body systems and communication complexity.
The operator Schmidt rank is the minimum number of terms required to express a state as a sum of elementary tensor factors. Here we provide a new proof of the fact that any bipartite mixed state with operator Schmidt rank two is separable, and can be written as a sum of two positive semidefinite matrices per site. Our proof uses results from the theory of free spectrahedra and operator systems, and illustrates the use of a connection between decompositions of quantum states and decompositions of nonnegative matrices. In the multipartite case, we prove that any Hermitian Matrix Product Density Operator (MPDO) of bond dimension two is separable, and can be written as a sum of at most four positive semidefinite matrices per site. This implies that these states can only contain classical correlations, and very few of them, as measured by the entanglement of purification. In contrast, MPDOs of bond dimension three can contain an unbounded amount of classical correlations.
We study six natural decompositions of mixed states in one spatial dimension: the matrix product density operator form, the local purification form, the separable decomposition (for separable states), and their three translational invariant analogs. For bipartite states diagonal in the computational basis, we show that these decompositions correspond to well-studied factorizations of an associated nonnegative matrix. Specifically, the first three decompositions correspond to the minimal factorization, the nonnegative factorization, and the positive semidefinite factorization. We also show that a symmetric version of these decompositions corresponds to the symmetric factorization, the completely positive factorization, and the completely positive semidefinite transposed factorization. We leverage this correspondence to characterize the six decompositions of mixed states.
Abstract. We show that states on tensor products of matrix algebras whose ranks are relatively small are almost surely entangled, but that states of maximum rank are not. More precisely, let M = Mm(C) and N = Mn(C) be full matrix algebras with m ≥ n, fix an arbitrary state ω of N, and let E(ω) be the set of all states of M ⊗N that extend ω. The space E(ω) contains states of rank r for every r = 1, 2,..., m · rank ω, and it has a filtration into compact subspaces E 1 (ω) ⊆ E 2 (ω) ⊆ · · · ⊆ E m·rank ω = E(ω), where E r (ω) is the set of all states of E(ω) having rank ≤ r. We show first that for every r, there is a real-analytic manifold V r, homogeneous under a transitive action of a compact group G r, which parameterizes E r (ω). The unique G r-invariant probability measure on V r promotes to a probability measure P r,ω on E r (ω), and P r,ω assigns probability 1 to states of rank r. The resulting probability space (E r (ω),P r,ω) represents “choosing a rank r extension of ω at random”. Main result: For every r = 1, 2,..., [rank ω/2], states of (E r (ω), P r,ω) are almost surely entangled. 1.
The tensor rank (also known as generalized Schmidt rank) of multipartite pure states plays an important role in the study of entanglement classifications and transformations. We employ powerful tools from the theory of homogeneous polynomials to investigate the tensor rank of symmetric states such as the tripartite state |W3>=1/√3(|100> + |010> + |001>) and its N-partite generalization |W(N)>. Previous tensor rank estimates are dramatically improved and we show that (i) three copies of |W3> have a rank of either 15 or 16, (ii) two copies of |W(N)> have a rank of 3N - 2, and (iii) n copies of |W(N)> have a rank of O(N). A remarkable consequence of these results is that certain multipartite transformations, impossible even probabilistically, can become possible when performed in multiple-copy bunches or when assisted by some catalyzing state. This effect is impossible for bipartite pure states.