Optimal single-copy estimation of quantum state moments: why $\mathrm{Tr}({\rho }^3)$ and $\mathrm{Tr}({\rho }^4)$ are equally hard

Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments $\mathrm{Tr}({\rho }^t)$, allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity $\mathrm{\Theta }(\sqrt{d})$ at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer $t\ge 2$: for any sufficiently small constant additive error, the optimal sample complexity is $$\mathrm{\Theta }\text{\hspace{0.17em}⁣}\left(d^{\frac{\lceil {\log }_{2}t\rceil }{1+\lceil {\log }_{2}t\rceil }}\right)$$ with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer $h\ge 1$, all moment orders $2^{h-1}<t\le 2^h$ share the same exponent. In particular, the third and fourth moments both require $\mathrm{\Theta }(d^{2\mathrm{/}3})$ copies. We also establish an $\mathrm{\Omega }(d^{1-1\mathrm{/}t})$ lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every $t\ge 4$. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond $\sqrt{d}$.