The subject of this thesis is learning and testing properties of mixed quantum states. A mixed state is described by a density matrix ρ ∈ ℂ ^dxd. In the standard model, one is given access to many identical copies of the mixed state, and the goal is to perform measurements on the copies to infer some information about ρ. In our problem, each copy of ρ plays a role analogous to a sample drawn from a probability distribution, and just as we aim to minimize sample complexity in classical statistics, here we aim to minimize copy complexity. Our results are:

• We give new upper bounds for the number of copies needed to learn the matrix ρ and the best low rank approximation to ρ, matching the lower bounds of [HHJ+16]. This settles the copy complexity of the quantum tomography problem (up to constant factors) and gives a first-of-its-kind principal-component-analysis-style guarantee for learning approximately low rank states. In addition, we give new upper bounds for the number of copies needed to learn the entire spectrum of ρ and the largest eigenvalues of ρ. We then show matching lower bounds for these latter problems for a popular spectrum learning algorithm, the empirical Young diagram algorithm of [ARS88, KW01].

• We consider testing properties of ρ and its spectrum in the standard property testing model [RS96, BFR+00]. We show matching upper and lower bounds for the number of copies needed to test if ρ is the "maximally mixed state". This can be viewed as the quantum analogue of Paninski's sharp bounds for classical uniformity-testing [Pan08]. In addition, we give a new upper bound for testing whether ρ is low rank. Finally, we give almost matching upper and lower bounds for the problem of distinguishing whether ρ is maximally mixed on a subspace of dimension r or of dimension r + Δ.

• We give a new and optimal bound on the expected length of the LIS in a random word. Furthermore, we show optimal bounds for the "shape" of the Young diagram resulting from applying the "RSK algorithm" to a random word.

• We prove a majorization theorem for the RSK algorithm applied to random words. It states, roughly, that random words drawn from more "top-heavy" dixstributions will tend to produce more "top-heavy" Young diagrams when the RSK algorithm is applied to them.

181 pages

Thesis Committee:
Ryan O'Donnell (Chair)
Anupam Gupta
Venkatesan Guruswami
Aram Harrow (Massachusetts Institute of Technology)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science