Efficient quantum tomography

In the quantum state tomography problem, one wishes to estimate an unknown $d$-dimensional mixed quantum state $ρ$, given few copies. We show that $O(d/ε)$ copies suffice to obtain an estimate $\hatρ$ that satisfies $\|\hatρ - ρ\|_F^2 \leq ε$ (with high probability). An immediate consequence is that $O(\mathrm{rank}(ρ) \cdot d/ε^2) \leq O(d^2/ε^2)$ copies suffice to obtain an $ε$-accurate estimate in the standard trace distance. This improves on the best known prior result of $O(d^3/ε^2)$ copies for full tomography, and even on the best known prior result of $O(d^2\log(d/ε)/ε^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 $ρ$. Our main result is that $O(k d/ε^2)$ copies suffice to output a rank-$k$ approximation $\hatρ$ whose trace distance error is at most $ε$ more than that of the best rank-$k$ approximator to $ρ$. This subsumes our above trace distance tomography result and generalizes it to the case when $ρ$ 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 $ρ$ can be estimated to trace-distance error $ε$ using $O(k^2/ε^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.