The Keyl–Werner algorithm is not optimal for spectrum estimation

For over two decades, the Keyl–Werner algorithm has been the standard method for estimating the spectrum (the set of eigenvalues) of a quantum state. While it is known to be asymptotically exact, its optimality has remained a central open question in quantum learning theory. Specifically, researchers have questioned whether spectrum estimation could be performed with fewer than the Theta(d^2) copies required for full state tomography. This paper addresses this question by developing a new algorithm that achieves a lower sample complexity, thereby resolving the long-standing uncertainty surrounding the optimality of the Keyl–Werner approach.

The authors introduce a new, fine-grained tomography guarantee that functions as a quantum analogue to relative-error bounds in classical statistics. In classical distribution estimation, the variance of an estimator scales with the probability of the outcome, allowing for more precise estimation of smaller values. The authors adapt this concept to the quantum setting by constructing an estimator where the error in a given direction |w> scales with the expectation <w|rho|w>. This "relative-error" bound allows the algorithm to effectively "bucket" eigenvalues, focusing resources on the relevant parts of the spectrum and bypassing the limitations of previous uniform-error tomography methods.

The primary contribution is an algorithm that estimates the spectrum of a d-dimensional quantum state to constant error in total variation distance using O(d^2 * (log log d / log d)^2) copies. This result provides the first improvement over the Keyl–Werner algorithm and disproves a 2016 conjecture by Wright, which suggested that the sample complexity could not be improved beyond a single factor of log(d). The authors also demonstrate that their relative-error bound is a powerful technical tool, yielding improved algorithms for principal component analysis in Bures distance and tomography in chi-squared divergence as corollaries.