Completely positive semidefinite rank

DOI10.1007/S10107-017-1198-4MaRDI QIDQ1785204zbMATH OpenOpenAlexFDO

Authors Anupam Prakash, Jamie Sikora, A. Varvitsiotis, Zhaohui Wei

Publication date 28 September 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.07199

zbMATH Keywords

Bell scenariocompletely positive semidefinite coneelliptopeLorentz conequantum behaviorquantum correlations

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03) Clifford algebras, spinors (15A66) Positive matrices and their generalizations; cones of matrices (15B48) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Convex programming (90C25)

Abstract: An $nimesn$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $dimesd$ Hermitian positive semidefinite matrices ${P_i}_{i=1}^n$ (for some $dge1$) such that $X_{ij}=mTr(P_i{P}_j),$ for all $i,jin1,ldots,n$. The cpsd-rank of a cpsd matrix is the smallest $dge1$ 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 $nge1,$ we construct a cpsd matrix of size $2n$ whose cpsd-rank is $2^{Omega(sqrtn)}$. 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.

Recommendations

• Matrices with high completely positive semidefinite rank
• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Minimal cp rank
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Positive semidefinite rank

Cites work

• A Note on Extreme Correlation Matrices
• Characterization of completely positive graphs
• Completely positive matrices associated withM-matrices
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Conic formulations of graph homomorphisms
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Extremal correlation matrices
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 48576 (Why is no real title available?)
• scientific article; zbMATH DE number 515467 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• Introduction to representation theory
• Lifts of Convex Sets and Cone Factorizations
• Linear conic formulations for two-party correlations and values of nonlocal games
• Lower bounds on the entanglement needed to play XOR non-local games
• Matrices with high completely positive semidefinite rank
• Matrix Analysis
• New approximations for the cone of copositive matrices and its dual
• New lower bounds and asymptotics for the cp-rank
• On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings
• On the copositive representation of binary and continuous nonconvex quadratic programs
• On the Matrix Equation X′X = A
• On the Problem of Hidden Variables in Quantum Mechanics
• On vector configurations that can be realized in the cone of positive matrices
• Positive semidefinite rank
• Quantum analogues of the Bell inequalities. The case of two spatially separated domains
• Symmetry, Representations, and Invariants

Cited in

(16)

• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Rational and real positive semidefinite rank can be different
• Algorithms for positive semidefinite factorization
• Positively factorizable maps
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Completely positive completely positive maps (and a resource theory for non-negativity of quantum amplitudes)
• Matrices with high completely positive semidefinite rank
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings
• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Some upper and lower bounds on PSD-rank
• Approximate completely positive semidefinite factorizations and their ranks
• Self-Dual Polyhedral Cones and Their Slack Matrices
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Semidefinite games
• Signed tropicalization of polar cones

This page was built for publication: Completely positive semidefinite rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785204)