Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
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 Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(√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(⌈log2 t⌉)/(1+⌈log2 t⌉)) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1, all moment orders 2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/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 Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥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 √d.
Related
- Quantum enhanced beam displacement estimation: sensitivity limits, optimal probes, and measurement schemes
- Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements
- Chern-number estimation: nearly optimal quantum algorithm and provable quantum speedup
- Optimal estimation of quantum boundary effect in cosmic string space-time
- Optimal Resource Scaling for Early Fault Tolerant Iterative Quantum Phase Estimation under Cost Error Tradeoffs
BibTeX
@misc{liu2026optimal,
title = {{Optimal single-copy estimation of quantum state moments: why $\operatornameTr(ρ^3)$ and $\operatornameTr(ρ^4)$ are equally hard}},
author = {Zhenhuan Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.37781},
eprint = {2609.37781},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37781},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal single-copy estimation of quantum state moments: why Tr(ρ^3) and Tr(ρ^4) are equally hard
AU - Zhenhuan Liu
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2609.37781
UR - https://arxiv.org/abs/2609.37781
AB - 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 Θ(√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^(⌈log_2 t⌉)/(1+⌈log_2 t⌉)) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1, all moment orders 2^h−1<t≤2^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≥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 √d.
ER -