Estimating Quantum Entropy

The entropy of a quantum system is a measure of its randomness, and has applications in measuring quantum entanglement. We study the problem of estimating the von Neumann entropy, S(ρ), and Rényi entropy, S α (ρ) of an unknown mixed quantum state ρ in d dimensions, given access to independent copies of ρ. We provide algorithms with copy complexity O(d 2/α ) for estimating Sα(ρ) for α <; 1, and copy complexity O(d 2 ) for estimating S(ρ), and S α (ρ) for non-integral α > 1. These bounds are at least quadratic in d, which is the order dependence on the number of copies required for estimating the entire state ρ. For integral α > 1, on the other hand, we provide an algorithm for estimating S α (ρ) with a sub-quadratic copy complexity of O(d 2-2/α ), and we show the optimality of the algorithms by providing a matching lower bound.