Quantum algorithm for estimating Renyi entropies of quantum states

Understand

We describe a quantum algorithm to estimate the $\alpha$-Renyi entropy of an unknown density matrix $\rho\in\mathcal{C}^{d\times d}$ for $\alpha\neq 1$ by combining the recent technique of quantum singular value transformations with the method of estimating normalised traces in the one clean qubit model.

• We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be non-singular.
• Our method outputs an estimate of the $\alpha$-Renyi entropy to additive precision $\epsilon$, using an expected total number $O\left(\frac{1}{(x\epsilon)^2}\right)$ of independent applications of a quantum circuit which coherently queries the input unitary $O\left(\frac{1}{\delta}\log \frac{d}{\epsilon}\right)$ times, in each case measuring a single output qubit.
• Here $\delta$ is a lower cutoff on the smallest eigenvalue of $\rho$ and $x=\frac{1}{d}\!\mathop{Tr}{\rho^\alpha}$.