Understand
We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum R\'{e}nyi entropy, trace distance, and fidelity.
- The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups.
- In particular, for $N$-dimensional quantum states of rank $r$, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error $\varepsilon$ have time complexity of $\tilde O(r/\varepsilon^2)$, $\tilde O(r^5/\varepsilon^6)$ and $\tilde O(r^{6.5}/\varepsilon^{7.5})$, respectively.
- By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity $\Omega(N)$, and the prior best one for fidelity has time complexity $\tilde O(r^{12.5}/\varepsilon^{13.5})$.