CMU-CS-16-108Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-16-108
John Wright May 2016 Ph.D. Thesis
Keywords:
Quantum tomography, property testing, longest increasing subsequences,
RSK algorithm, Schur-Weyl duality
The subject of this thesis is learning and testing properties of mixed quantum
states. A mixed state is described by a density matrix ρ.
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
Frank Pfenning, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection |