Resource-efficient algorithm for estimating the trace of quantum state powers

Estimating the trace of quantum state powers, $\text{Tr}({\rho }^k)$, for $k$ identical quantum states is a fundamental task with numerous applications in quantum information processing, including nonlinear function estimation of quantum states and entanglement detection. On near-term quantum devices, reducing the required quantum circuit depth, the number of multi-qubit quantum operations, and the copies of the quantum state needed for such computations is crucial. In this work, inspired by the Newton-Girard method, we significantly improve upon existing results by introducing an algorithm that requires only $\mathcal{O}(\tilde{r})$ qubits and $\mathcal{O}(\tilde{r})$ multi-qubit gates, where $\tilde{r}=\min \{\text{rank}(\rho ),\lceil \ln \left(2k\mathrm{/}\epsilon \right)\rceil \}$. This approach is efficient, as it employs the $\tilde{r}$-entangled copy measurement instead of the conventional $k$-entangled copy measurement, while asymptotically preserving the known sample complexity upper bound. Furthermore, we prove that estimating $\{\text{Tr}({\rho }^i){\}}_{i=1}^{\tilde{r}}$ is sufficient to approximate $\text{Tr}({\rho }^k)$ even for large integers $k>\tilde{r}$. This leads to a rank-dependent complexity for solving the problem, providing an efficient algorithm for low-rank quantum states while also improving existing methods when the rank is unknown or when the state is not low-rank. Building upon these advantages, we extend our algorithm to the estimation of $\text{Tr}(M{\rho }^k)$ for arbitrary observables and $\text{Tr}({\rho }^k{\sigma }^l)$ for multiple quantum states.