In the problem of quantum state learning, one is given a small number of "samples" of a quantum state, and the goal is to output a good estimate of the quantum state. This is a problem which is not only of theoretical interest, but is also commonly used in current-day implementation and verification of quantum technologies. In this thesis, we show the first optimal quantum algorithm for this problem. In addition, we give optimal algorithms for the related problems of testing and learning specific properties of quantum states. Our results make use of a new connection between quantum state learning and longest increasing subsequences of random words, a famous topic in combinatorics dating back to a 1935 paper of Erdős and Szekeres. Motivated by this connection, we show new and optimal bounds on the length of the longest increasing subsequence of a random word.
Thesis Committee: Ryan O’Donnell (Chair) Anupam Gupta Venkatesan Guruswami Aram Harrow (Massachusetts Institute of Technology)