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

Abstract

Estimating the trace of quantum state powers, Tr(ρ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 O(r~) qubits and O(r~) multi-qubit gates, where r~=min{rank(ρ),⌈ln⁡(2k/ϵ)⌉}. This approach is efficient, as it employs the 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 {Tr(ρi)}i=1r~ is sufficient to approximate Tr(ρk) even for large integers k>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 Tr(Mρk) for arbitrary observables and Tr(ρkσl) for multiple quantum states.