New Quantum Algorithms for Computing Quantum Entropies and Distances

We propose a series of quantum algorithms forcomputing a wide range of quantum entropies and distances,including the von Neumann entropy, quantum R & eacute;nyi entropy,trace distance, and fidelity. The proposed algorithms significantlyoutperform the prior best (and even quantum) ones in thelow-rank case, some of which achieve exponential speedups.In particular, forN-dimensional quantum states of rankr, ourproposed quantum algorithms for computing the von Neumannentropy, trace distance and fidelity within additive error epsilon havetime complexity of O(r/epsilon(2)), O(r(5)/epsilon(6))and O(r(6.5)/epsilon(7.5)),respectively. By contrast, prior quantum algorithms for the vonNeumann entropy and trace distance usually have time complex-ity ohm (N), and the prior best one for fidelity has time complexity O(r(12.5)/epsilon(13.5)). The key idea of our quantum algorithms isto extend block-encoding from unitary operators in previouswork to quantum states (i.e., density operators). It is realized bydeveloping several convenient techniques to manipulate quantumstates and extract information from them. The advantage of ourtechniques over the existing methods is that no restrictions ondensity operators are required; in sharp contrast, the previousmethods usually require a lower bound on the minimal non-zeroeigenvalue of density operators