{"id":"arxiv/2607.27117","url":"https://arxiv.org/abs/2607.27117","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"The Keyl-Werner algorithm is not optimal for spectrum estimation","domain":"quant-ph","source":"arxiv","authors":["Angelos Pelecanos","Jack Spilecki","Ewin Tang","John Wright"],"reviews":0,"subject":"quant-ph","summary":"We give an algorithm which, given $n = O(d^2 \\cdot (\\log\\log(d)/\\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(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 = Θ(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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-29","reactions":{}}