Yukun Zhang, Yusen Wu, You Zhou, Xiao Yuan (Sep 03 2025).

Abstract: A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $\mathrm{Tr}(\rho^k O)$. Intuitively, one expects that computing a $k$-th order quantity generally requires $O(k)$ copies of the state $\rho$, and we rigorously establish this lower bound under sample access to $\rho$. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of $\rho$, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of $\Theta(\sqrt{k})$, and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory -- specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling, and evaluating other multiple nonlinear quantum observables with classical shadows.

Arxiv: https://arxiv.org/abs/2509.01571