Improved sample upper and lower bounds for trace estimation of quantum state powers

摘要

As often emerges in various basic quantum properties such as entropy, the trace of quantum state powers tr(ρ^q) has attracted a lot of attention. The recent work of Liu and Wang (SODA 2025) showed that tr(ρ^q) can be estimated to within additive error ε with a dimension-independent sample complexity of O(1/ε^3+2/q-1) for any constant q > 1, where only an Ω(1/ε) lower bound was given. In this paper, we significantly improve the sample complexity of estimating tr(ρ^q) in both the upper and lower bounds. In particular: - For q > 2, we settle the sample complexity with matching upper and lower bounds Θ(1/ε^2). - For 1 < q < 2, we provide an upper bound O(1/ε^2/q-1), with a lower bound Ω(1/ε^max{1/q-1, 2}) for dimension-independent estimators, implying there is only room for a quadratic improvement. Our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling, in sharp contrast to the prior approach based on quantum singular value transformation and samplizer.