Two random matrix problems inspired by quantum information Speaker(s): Andris Ambainis
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 MarcenkoPastur law determines (up to small corrections) not only the largest eigenvalue ((1+sqrt{p/d^k})^2) but the smallest eigenvalue (min(0,1sqrt{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 MarcenkoPastur 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.
Date: 05/07/2010  3:30 pm
