Computer Science Department
School of Computer Science, Carnegie Mellon University
How to Learn a Quantum State
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 ρ ∈ ℂ 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:
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 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
- 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.
Ryan O'Donnell (Chair)
Aram Harrow (Massachusetts Institute of Technology)
Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science