Thilo Scharnhorst

We show that $n = \Omega(rd/\epsilon^2)$ copies are necessary to learn a rank $r$ mixed state $\rho \in \C^{d \times d}$ up to error~$\epsilon$ in trace distance. This matches the upper bound of $n = O(rd/\epsilon^2)$ from~\cite{OW16} and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as \emph{projector tomography}, in which $\rho$ is promised to be of the form $\rho = P/r$, where $P \in \C^{d \times d}$ is a rank $r$ projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error $\epsilon$ in trace distance to an algorithm which learns to error $O(\epsilon)$ in the more stringent Bures distance.