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

Quantum 9, 1832 (2025).

https://doi.org/10.22331/q-2025-08-27-1832

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}(widetilde{r})$ qubits and $mathcal{O}(widetilde{r})$ multi-qubit gates, where $widetilde{r} = minleft{text{rank}(rho), leftlceillnleft({2k}/{epsilon}right)rightrceilright}$. 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 gt widetilde{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}(Mrho^k)$ for arbitrary observables and $text{Tr}(rho^k sigma^l)$ for multiple quantum states.