Some upper and lower bounds on PSD-rank

Springer Science and Business Media LLC - Tập 162 - Trang 495-521 - 2016
Troy Lee1, Zhaohui Wei1, Ronald de Wolf2
1School of Physics and Mathematical Sciences, Nanyang Technological University and Centre for Quantum Technologies, Singapore, Singapore
2QuSoft, CWI and University of Amsterdam, Amsterdam, The Netherlands

Tóm tắt

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, 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.

Tài liệu tham khảo

Gouveia, J., Parrilo, P., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248–264 (2013). arXiv:1111.3164 Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R. and de Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 16(2), 2015. Earlier version in STOC’12. arXiv:1111.0837 Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441–466 (1991) Rothvoß, T.: The matching polytope has exponential extension complexity. In: Proceedings of 46th ACM STOC, pp. 263–272 (2014) Lee, J., Steurer, D. and Raghavendra, P.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of 47th ACM STOC, pp. 567–576 (2015). arXiv:1411.6317 Lee, T. and Wei, Z.: The square root rank of the correlation polytope is exponential (2014). arXiv:1411.6712 Conforti, M., Faenza, Y., Fiorini, S. and Tiwary, H.R.: Extended formulations, non-negative factorizations and randomized communication protocols. In: 2nd International Symposium on Combinatorial Optimization, pp. 129–140 (2012). arXiv:1105.4127 Zhang, S.: Quantum strategic game theory. In: Proceedings of the 3rd Innovations in Theoretical Computer Science, pp 39–59 (2012). arXiv:1012.5141 Jain, R., Shi, Y., Wei, Z., Zhang, S.: Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Trans. Inf. Theory 59, 5171–5178 (2013) Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997) Lee, T. and Theis, D.O.: Support based bounds for positive semidefinite rank (2012). arXiv:1203.3961 Sikora, J., Varvitsiotis, A. and Wei, Z.: On the minimum dimension of a Hilbert space needed to generate a quantum correlation (2015). arXiv:1507.00213 Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2), 193–205 (2001) Fawzi, H., Parrilo, P.: Lower bounds on nonnegative rank via nonnegative nuclear norms. Math. Program., Ser. B 153(1), 41–66 (2015). arXiv:1210.6970 Fawzi, H., Gouveia, J., Parrilo, P., Robinson, R., Thomas, R.: Positive semidefinite rank. Math. Program., Ser. B 153(1), 133–177 (2015). arXiv:1407.4095 Alon, N.: Perturbed identity matrices have high rank: proof and applications. Combin., Prob., Comput. 18, 3–15 (2009)