Intuitively, if a density operator has small rank, then it should be easier

to estimate from experimental data, since in this case only a few eigenvectors

need to be learned. We prove two complementary results that confirm this

intuition. First, we show that a low-rank density matrix can be estimated using

fewer copies of the state, i.e., the sample complexity of tomography decreases

with the rank. Second, we show that unknown low-rank states can be

reconstructed from an incomplete set of measurements, using techniques from

compressed sensing and matrix completion. These techniques use simple Pauli

measurements, and their output can be certified without making any assumptions

about the unknown state.

We give a new theoretical analysis of compressed tomography, based on the

restricted isometry property (RIP) for low-rank matrices. Using these tools, we

obtain near-optimal error bounds, for the realistic situation where the data

contains noise due to finite statistics, and the density matrix is full-rank

with decaying eigenvalues. We also obtain upper-bounds on the sample complexity

of compressed tomography, and almost-matching lower bounds on the sample

complexity of any procedure using adaptive sequences of Pauli measurements.

Using numerical simulations, we compare the performance of two compressed

sensing estimators with standard maximum-likelihood estimation (MLE). We find

that, given comparable experimental resources, the compressed sensing

estimators consistently produce higher-fidelity state reconstructions than MLE.

In addition, the use of an incomplete set of measurements leads to faster

classical processing with no loss of accuracy.

Finally, we show how to certify the accuracy of a low rank estimate using

direct fidelity estimation and we describe a method for compressed quantum

process tomography that works for processes with small Kraus rank.