The Keyl-Werner algorithm is not optimal for spectrum estimation

We give an algorithm which, given $n=O(d^2\cdot (\log \log (d)\mathrm{/}\log (d){)}^2)$ copies of $\rho$, estimates the eigenvalues of $\rho$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $\mathrm{\Theta }(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n=\mathrm{\Theta }(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $\mathrm{\mid }w⟩$ scales with $⟨w\mathrm{\mid }\rho \mathrm{\mid }w⟩$ for all directions simultaneously. From this stronger “relative-error” bound, we recover better algorithms for principal component analysis in Bures distance and tomography in ${\chi }^2$-divergence as corollaries.