The Keyl-Werner algorithm is not optimal for spectrum estimation

Abstract

We give an algorithm which, given $n=O(d^2\cdot (\log \log (d)/\log (d){)}^2)$ copies of $\ddot{I}$, estimates the eigenvalues of $\ddot{I}$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $\hat{I}˜(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=\hat{I}˜(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 $|w⟩$ scales with $⟨w|\ddot{I}|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 $\ddot{I}{‡}^2$-divergence as corollaries.

58 pages

Topics & keywords