  Estimating the trace of powers of identical $k$ density matrices (i.e.,
$\text{Tr}(\rho^k)$) is a crucial subroutine for many applications such as
calculating nonlinear functions of quantum states, preparing quantum Gibbs
states, and mitigating quantum errors. Reducing the requisite number of qubits
and gates is essential to fit a quantum algorithm onto near-term quantum
devices. Inspired by the Newton-Girard method, we developed an algorithm that
uses only $\mathcal{O}(r)$ qubits and $\mathcal{O}(r)$ multi-qubit gates, where
$r$ is the rank of $\rho$. We prove that the estimation of
$\{\text{Tr}(\rho^i)\}_{i=1}^r$ is sufficient for estimating the trace of
powers with large $k > r$. With these advantages, our algorithm brings the
estimation of the trace of powers closer to the capabilities of near-term
quantum processors. We show that our results can be generalized for estimating
$\text{Tr}(M\rho^k)$, where $M$ is an arbitrary observable, and demonstrate the
advantages of our algorithm in several applications.
