Completely positive semidefinite rank

Abstract

An $n\times n$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $d\times d$ Hermitian positive semidefinite matrices $\{P_i{\}}_{i=1}^n$ (for some $d\ge 1$) such that $X_{ij}=\mathrm{Tr}(P_i{P}_j),$ for all $i,j\in \{1,\dots ,n\}$. The cpsd-rank of a cpsd matrix is the smallest $d\ge 1$ for which such a representation is possible. In this work we initiate the study of the cpsd-rank which we motivate twofold. First, the cpsd-rank is a natural non-commutative analogue of the completely positive rank of a completely positive matrix. Second, we show that the cpsd-rank is physically motivated as it can be used to upper and lower bound the size of a quantum system needed to generate a quantum behavior. In this work we present several properties of the cpsd-rank. Unlike the completely positive rank which is at most quadratic in the size of the matrix, no general upper bound is known on the cpsd-rank of a cpsd matrix. In fact, we show that the cpsd-rank can be exponential in terms of the size. Specifically, for any $n\ge 1,$ we construct a cpsd matrix of size $2n$ whose cpsd-rank is $2^{\Omega (\sqrt{n})}$. Our construction is based on Gram matrices of Lorentz cone vectors, which we show are cpsd. The proof relies crucially on the connection between the cpsd-rank and quantum behaviors. In particular, we use a known lower bound on the size of matrix representations of extremal quantum correlations which we apply to high-rank extreme points of the $n$-dimensional elliptope. Lastly, we study cpsd-graphs, i.e., graphs $G$ with the property that every doubly nonnegative matrix whose support is given by $G$ is cpsd. We show that a graph is cpsd if and only if it has no odd cycle of length at least $5$ as a subgraph. This coincides with the characterization of cp-graphs.

29 pages including appendix. Comments welcome

References in corpus (1)

• Matrices with high completely positive semidefinite rank

Cited by in corpus (4)

• Algorithms for Positive Semidefinite Factorization
• Structure of the set of quantum correlators via semidefinite programming
• Self-dual polyhedral cones and their slack matrices
• Completely positive completely positive maps (and a resource theory for non-negativity of quantum amplitudes)