Rank Is All You Need: Estimating the Trace of Powers of Density Matrices

Estimating the trace of powers of identical k density matrices (i.e., Tr(ρᵏ)) 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 O(r) qubits and O(r) multi-qubit gates, where r is the rank of ρ. We prove that the estimation of (ρⁱ)\ᵢ₌₁ʳ 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 Tr(Mρᵏ), where M is an arbitrary observable, and demonstrate the advantages of our algorithm in several applications.