Spectrum Estimation is Almost as Hard as Tomography
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 Ω(d2−γ) 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.
Related
- Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
- Hamiltonian Particle Dynamics in Fusion Plasmas: Orbital Tomography and Spectrum Analysis for Energy and Momentum Transport under Resonant Non-Axisymmetric Perturbations
- Optimal spectrum estimation
- Q-SPARSE: Quantum Subspace Projection for Near-Field Angle-Range Spectrum Estimation
- Robustness of quantum spectrum estimation: weak Schur sampling under noisy inputs
BibTeX
@misc{fanizza2026spectrum,
title = {{Spectrum Estimation is Almost as Hard as Tomography}},
author = {Marco Fanizza and Ryan O'Donnell and Chirag Wadhwa},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.29680},
eprint = {2607.29680},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.29680},
}
RIS
TY - UNPB
TI - Spectrum Estimation is Almost as Hard as Tomography
AU - Marco Fanizza
AU - Ryan O'Donnell
AU - Chirag Wadhwa
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2607.29680
UR - https://arxiv.org/abs/2607.29680
AB - 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.
ER -