Optimal single-copy estimation of quantum state moments: why Tr(rho 3) and 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 Tr(ρ t), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(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 2: for any sufficiently small constant additive error, the optimal sample complexity is Θ! (d 2 t over 1+ 2 t) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h at least1, all moment orders 2 h-1<t at most2 h share the same exponent. In particular, the third and fourth moments both require Θ(d 2/3) copies. We also establish an Ω(d 1-1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t at least4. 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.