  In the quantum state tomography problem, one wishes to estimate an unknown
$d$-dimensional mixed quantum state $\rho$, given few copies. We show that
$O(d/\epsilon)$ copies suffice to obtain an estimate $\hat{\rho}$ that
satisfies $\|\hat{\rho} - \rho\|_F^2 \leq \epsilon$ (with high probability). An
immediate consequence is that $O(\mathrm{rank}(\rho) \cdot d/\epsilon^2) \leq
O(d^2/\epsilon^2)$ copies suffice to obtain an $\epsilon$-accurate estimate in
the standard trace distance. This improves on the best known prior result of
$O(d^3/\epsilon^2)$ copies for full tomography, and even on the best known
prior result of $O(d^2\log(d/\epsilon)/\epsilon^2)$ copies for spectrum
estimation. Our result is the first to show that nontrivial tomography can be
obtained using a number of copies that is just linear in the dimension.
  Next, we generalize these results to show that one can perform efficient
principal component analysis on $\rho$. Our main result is that $O(k
d/\epsilon^2)$ copies suffice to output a rank-$k$ approximation $\hat{\rho}$
whose trace distance error is at most $\epsilon$ more than that of the best
rank-$k$ approximator to $\rho$. This subsumes our above trace distance
tomography result and generalizes it to the case when $\rho$ is not guaranteed
to be of low rank. A key part of the proof is the analogous generalization of
our spectrum-learning results: we show that the largest $k$ eigenvalues of
$\rho$ can be estimated to trace-distance error $\epsilon$ using
$O(k^2/\epsilon^2)$ copies. In turn, this result relies on a new coupling
theorem concerning the Robinson-Schensted-Knuth algorithm that should be of
independent combinatorial interest.
