arXiv:2609.37781
Optimal single-copy estimation of quantum state moments: why $\operatorname{Tr}(ρ^3)$ and $\operatorname{Tr}(ρ^4)$ are equally hard
Zhenhuan Liu
Abstract
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 $\operatorname{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\ge 2$: for any sufficiently small constant additive error, the optimal sample complexity is \[ Θ\!\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\geq1$, all moment orders $2^{h-1}<t\leq2^h$ share the same exponent. In particular, the third and fourth moments both require $Θ(d^{2/3})$ copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. 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\geq4$. 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$.
AI Summary
The paper determines the copy complexity of estimating $p_t(\rho)=\operatorname{Tr}(\rho^t)$ for an unknown $d$-dimensional state using arbitrary single-copy measurements, with classical adaptation but no quantum memory between copies. For every fixed integer $t\geq2$ and sufficiently small constant additive error, the optimal worst-case complexity is $\Theta(d^{h/(h+1)})$, where $h=\lceil\log_2t\rceil$, at constant success probability. Thus orders three and four both require $\Theta(d^{2/3})$ copies, and orders five through eight require $\Theta(d^{3/4})$. For nonadaptive single-copy POVMs, the complexity is instead $\Theta(d^{1-1/t})$, establishing an adaptive advantage for every $t\geq4$. The upper bound learns low-rank filters from preliminary measurement outcomes. Filtered-state moments approximate moments of $(\rho+x\rho^2)/(1+xp_2)$; polynomial interpolation recovers higher moments. Recursion doubles the accessible moment order while transforming the complexity exponent as $a\mapsto1/(2-a)$. The lower bound directly compares moment-matched random-state ensembles along a smooth spectral path. Moment matching cancels low-degree likelihood-derivative terms, while martingale cycle estimates control adaptive transcripts; conditional independence gives stronger nonadaptive bounds. Reductions extend the dimension scaling to ordered multistate overlaps, weighted moments, and partial-transpose moments when one subsystem has fixed dimension, and give a fixed-rank spectrum-estimation upper bound. Distributed estimation of $\operatorname{Tr}[(\rho\sigma)^t]$ has complexity $\Theta(\sqrt d)$ when each party can jointly measure its own copies. Results concern fixed order and additive accuracy; constants can depend on both. Precision scaling, relative error, and quantum-memory tradeoffs remain unresolved.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 58 pages, 1 figure. In the revised version, we have streamlined the arguments in the proofs and added a new application