Beating full state tomography for unentangled spectrum estimation

How many copies of a mixed state \(\rho \in \mathbb{C}^{d \times d}\) are needed to learn its spectrum? To date, the best known algorithms for spectrum estimation require as many copies as full state tomography, suggesting the possibility that learning a state's spectrum might be as difficult as learning the entire state. We show that this is not the case in the setting of unentangled measurements, by giving a spectrum estimation algorithm that uses \(n = O\left(d^{3} \cdot (\log \log(d) / \log(d))^{4}\right)\) copies of \(\rho\), which is asymptotically fewer than the \(n = \Omega(d^{3})\) copies necessary for full state tomography. Our algorithm is inspired by the technique of local moment matching from classical statistics, and shows how it can be applied in the quantum setting.