Optimal spectrum estimation
Abstract
We prove that the spectrum of an unknown d-dimensional quantum state can be estimated to error ε in total variation distance using O (d2min{ 1/((εlog d)4), 1/((εlog d)2) }) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of d in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.
Related
BibTeX
@misc{bakshi2026optimal,
title = {{Optimal spectrum estimation}},
author = {Ainesh Bakshi and Apoorv Vikram Singh and Xinyu Tan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30171},
eprint = {2609.30171},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30171},
}
RIS
TY - UNPB
TI - Optimal spectrum estimation
AU - Ainesh Bakshi
AU - Apoorv Vikram Singh
AU - Xinyu Tan
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30171
UR - https://arxiv.org/abs/2609.30171
AB - We prove that the spectrum of an unknown d-dimensional quantum state can be estimated to error ε in total variation distance using O (d^2min{ 1/((εlog d)^4), 1/((εlog d)^2) }) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of d in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.
ER -