Two random matrix problems inspired by quantum information

Abstract

In this talk, I describe two cases in which questions in quantum information theory have lead me to random matrices. In the first case, analyzing a protocol for quantum cryptography lead us to the following question: what is the largest eigenvalue of a sum of p random product states in (C^d)^{otimes k}, where k and p/d^k are fixed while d grows? When k=1, the Marcenko-Pastur law determines (up to small corrections) not only the largest eigenvalue ((1+sqrt{p/d^k})^2) but the smallest eigenvalue (min(0,1-sqrt{p/d^k})^2) and the spectral density in between. We use the method of moments to show that for k>1 the largest eigenvalue is still approximately (1+sqrt{p/d^k})^2 and the spectral density approaches that of the Marcenko-Pastur law, generalizing the random matrix theory result to the random tensor case. In the second case, attempting to design a quantum algorithm lead us to the following question. Consider a random matrix M in which entries in some set S are always 0 and other entries are picked i.i.d. from some distribution. What is the expected value of the condition number of this random matrix? We have shown that there are sets S such that, with high probability M is nonsingular but has a very high condition number (2^{sqrt(n)} where n is the dimension of the matrix M). The first part is a joint work with Aram Harrow and Matthew Hastings and has appeared as arxiv preprint 0910.0472.