Completely positive semidefinite rank

An n× n matrix X is called completely positive semidefinite (cpsd) if there exist d× d Hermitian positive semidefinite matrices {Pi}i=1n (for some d≥ 1) such that Xij= Tr (PiPj) , for all i, j∈ { 1 , … , n}. The cpsd-rank of a cpsd matrix is the smallest d≥ 1 for which such a representation is possi...

Full description

Saved in:
Bibliographic Details
Main Authors: Prakash, Anupam, Sikora, Jamie, Varvitsiotis, Antonios, Wei, Zhaohui
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/139101
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-139101
record_format dspace
spelling sg-ntu-dr.10356-1391012020-05-15T07:28:18Z Completely positive semidefinite rank Prakash, Anupam Sikora, Jamie Varvitsiotis, Antonios Wei, Zhaohui School of Physical and Mathematical Sciences Centre for Quantum Technologies Science::Mathematics Completely Positive Semidefinite Cone CPSD-rank An n× n matrix X is called completely positive semidefinite (cpsd) if there exist d× d Hermitian positive semidefinite matrices {Pi}i=1n (for some d≥ 1) such that Xij= Tr (PiPj) , for all i, j∈ { 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Ω(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. NRF (Natl Research Foundation, S’pore) MOE (Min. of Education, S’pore) 2020-05-15T07:28:18Z 2020-05-15T07:28:18Z 2017 Journal Article Prakash, A., Sikora, J., Varvitsiotis, A., & Wei, Z. (2018). Completely positive semidefinite rank. Mathematical Programming, 171(1-2), 397-431. doi:10.1007/s10107-017-1198-4 0025-5610 https://hdl.handle.net/10356/139101 10.1007/s10107-017-1198-4 2-s2.0-85030685486 1-2 171 397 431 en Mathematical Programming © 2017 Springer-Verlag GmbH Germany and Mathematical Optimization Society. All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Science::Mathematics
Completely Positive Semidefinite Cone
CPSD-rank
spellingShingle Science::Mathematics
Completely Positive Semidefinite Cone
CPSD-rank
Prakash, Anupam
Sikora, Jamie
Varvitsiotis, Antonios
Wei, Zhaohui
Completely positive semidefinite rank
description An n× n matrix X is called completely positive semidefinite (cpsd) if there exist d× d Hermitian positive semidefinite matrices {Pi}i=1n (for some d≥ 1) such that Xij= Tr (PiPj) , for all i, j∈ { 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Ω(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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Prakash, Anupam
Sikora, Jamie
Varvitsiotis, Antonios
Wei, Zhaohui
format Article
author Prakash, Anupam
Sikora, Jamie
Varvitsiotis, Antonios
Wei, Zhaohui
author_sort Prakash, Anupam
title Completely positive semidefinite rank
title_short Completely positive semidefinite rank
title_full Completely positive semidefinite rank
title_fullStr Completely positive semidefinite rank
title_full_unstemmed Completely positive semidefinite rank
title_sort completely positive semidefinite rank
publishDate 2020
url https://hdl.handle.net/10356/139101
_version_ 1681056768153616384