John Wright

How to Learn a Quantum State Degree Type: Ph.D. in Computer Science
Advisor(s): Ryan O'Donnell
Graduated: May 2016

Abstract:

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 + Δ.

Our quantum results exploit a new connection to the combinatorial subject of longest increasing subsequences (LISes) of random words and require us to prove new results in this area. These results include:

• 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.

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

Keywords:
Quantum tomography, property testing, longest increasing subsequences, RSK algorithm, Schur-Weyl duality