Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.

arXiv.org e-Print archive
This work was funded by the European Commission 7th Framework Programme; grant id erc/615307 - Progress in quantum computing: Algorithms, communication, and applications (QPROGRESS)
Algorithms and Complexity

Lee, T. J, Wei, Z, & de Wolf, R.M. (2014). Some upper and lower bounds on PSD-rank. arXiv.org e-Print archive.