{"id":"arxiv/2607.29680","url":"https://arxiv.org/abs/2607.29680","tags":["quant-ph","cs.DS"],"score":0,"title":"Spectrum Estimation is Almost as Hard as Tomography","domain":"quant-ph","source":"arxiv","authors":["Marco Fanizza","Ryan O'Donnell","Chirag Wadhwa"],"reviews":0,"subject":"quant-ph","summary":"We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}