Sample-optimal Tomography of Quantum States

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples. Previously, it was known only that estimating states to error ie in trace distance required O(dr2/ie2) copies for a d-dimensional density matrix of rank r. Here, we give a measurement scheme (POVM) that uses O( (dr/ d ) ln(d/d) ) copies to estimate r to error d in infidelity. This implies O( (dr / ie2)* ln(d/ie) ) copies suffice to achieve error ie in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n. We also use the Holevo bound from quantum information theory to prove a lower bound of O(dr/ie2)/ log(d/rie) copies needed to achieve error ie in trace distance. This implies a lower bound O(dr/d)/log(d/rd) for the estimation error d in infidelity. These match our upper bounds up to log factors. Our techniques can also show an O(r2d/d) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such "product" measurements have asymptotically suboptimal scaling with d and r.