2025/05/14 by Chen, Kean, Wang, Qisheng · 4 citations
#FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2505.09563
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 \widetilde 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 \widetilde Θ(1/ε2). - For 1 < q < 2, we provide an upper bound \widetilde 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.