  For two unknown quantum states $\rho$ and $\sigma$ in an $N$-dimensional
Hilbert space, computing their fidelity $F(\rho,\sigma)$ is a basic problem
with many important applications in quantum computing and quantum information,
for example verification and characterization of the outputs of a quantum
computer, and design and analysis of quantum algorithms. In this Letter, we
propose a quantum algorithm that solves this problem in $\text{poly}(\log (N),
r)$ time, where $r$ is the lower rank of $\rho$ and $\sigma$. This algorithm
exhibits an exponential improvement over the best-known algorithm (based on
quantum state tomography) in $\text{poly}(N, r)$ time.
