Results 1 
3 of
3
Positive semidefinite rank
, 2014
"... Let M ∈ Rp×q be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices Ai, Bj of size k × k such that Mij = trace(AiBj). The psd rank has many appealing geometric interpretations, including semidefinite re ..."
Abstract

Cited by 6 (0 self)
 Add to MetaCart
Let M ∈ Rp×q be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices Ai, Bj of size k × k such that Mij = trace(AiBj). The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and informationtheoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects.
Linear conic formulations for twoparty correlations and values of nonlocal games
"... Abstract In this work we study the sets of twoparty correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. We show that the sets of classical, quantum, nosignaling and unrestricted correlations can be expressed as projections ..."
Abstract
 Add to MetaCart
(Show Context)
Abstract In this work we study the sets of twoparty correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. We show that the sets of classical, quantum, nosignaling and unrestricted correlations can be expressed as projections of affine sections of appropriate convex cones. As a byproduct, we identify a spectrahedral outer approximation to the set of quantum correlations which is contained in the first level of the Navascués, Pironio and Acín (NPA) hierarchy and also a sufficient condition for the set of quantum correlations to be closed. Furthermore, by our conic formulations, the value of a nonlocal game over the sets of classical, quantum, nosignaling and unrestricted correlations can be cast as a linear conic program. This allows us to show that a semidefinite programming upper bound to the classical value of a nonlocal game introduced by Feige and Lovász is in fact an upper bound to the quantum value of the game and moreover, it is at least as strong as optimizing over the first level of the NPA hierarchy. Lastly, we show that deciding the existence of a perfect quantum (resp. classical) strategy is equivalent to deciding the feasibility of a linear conic program over the cone of completely positive semidefinite matrices (resp. completely positive matrices). By specializing the results to synchronous nonlocal games, we recover the conic formulations for various quantum and classical graph parameters that were recently derived in the literature.