Completely positive semidefinite rank

• 成果类型: Article
• 署名作者: Prakash, Anupam; Sikora, Jamie; Varvitsiotis, Antonios; Wei, Zhaohui
• 署名单位: Nanyang Technological University; National University of Singapore; Nanyang Technological University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1198-4
• 发表日期: 2018
• 页码: 397-431
• 关键词: conic formulations; matrices; approximations; optimization; PROGRAMS

摘要

An n x n matrix X is called completely positive semidefinite (cpsd) if there exist d x d Hermitian positive semidefinite matrices {P-i}(i=1)(n) (for some d >= 1) such that X-ij = Tr(P-i P-j), for all i, j is an element of{1,..., n}. The cpsd-rank of a cpsd matrix is the smallest d >= 1 for which such a representation is possible. In this work we initiate the study of the cpsd-rank which we motivate in two ways. 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 sub-exponential in terms of the size. Specifically, for any n >= 1, we construct a cpsd matrix of size 2n whose cpsd-rank is 2(Omega(root 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.