Spectrum Estimation is Almost as Hard as Tomography
2026-07-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors investigate how many copies of an unknown quantum state are needed to accurately estimate its key features like the spectrum (eigenvalues), entropy, or to test its rank. They show that for quantum states of dimension d, at least about d squared copies are necessary for these tasks, even allowing a small error. To prove this, they create difficult examples using special random projectors and use advanced math tools called Jucys--Murphy elements to analyze these states. Their method shows that certain states are nearly impossible to distinguish unless you have many samples, establishing strong lower bounds on the sample complexity required.
Quantum stateSample complexitySpectrum estimationVon Neumann entropyRank-testingHaar-random projectorsJucys--Murphy elementsSymmetric group algebraf-divergenceMoment-matching
Authors
Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa
Abstract
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 novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.