  It is a fundamental problem to decide how many copies of an unknown mixed
quantum state are necessary and sufficient to determine the state. Previously,
it was known only that estimating states to error $\epsilon$ in trace distance
required $O(dr^2/\epsilon^2)$ copies for a $d$-dimensional density matrix of
rank $r$. Here, we give a theoretical measurement scheme (POVM) that requires
$O (dr/ \delta ) \ln (d/\delta) $ copies of $\rho$ to error $\delta$ in
infidelity, and a matching lower bound up to logarithmic factors. This implies
$O( (dr / \epsilon^2) \ln (d/\epsilon) )$ copies suffice to achieve error
$\epsilon$ in trace distance. We also prove that for independent (product)
measurements, $\Omega(dr^2/\delta^2) / \ln(1/\delta)$ copies are necessary in
order to achieve error $\delta$ in infidelity. For fixed $d$, our measurement
can be implemented on a quantum computer in time polynomial in $n$.
