  Fidelity is a fundamental measure for the closeness of two quantum states,
which is important both from a theoretical and a practical point of view. Yet,
in general, it is difficult to give good estimates of fidelity, especially when
one works with mixed states over Hilbert spaces of very high dimension.
Although, there has been some progress on fidelity estimation, all prior work
either requires a large number of identical copies of the relevant states, or
relies on unproven heuristics. In this work, we improve on both of these
aspects by developing new and efficient quantum algorithms for fidelity
estimation with provable performance guarantees in case at least one of the
states is approximately low-rank. Our algorithms use advanced quantum linear
algebra techniques, such as the quantum singular value transformation, as well
as density matrix exponentiation and quantum spectral sampling. As a
complementary result, we prove that fidelity estimation to any non-trivial
constant additive accuracy is hard in general, by giving a sample complexity
lower bound that depends polynomially on the dimension. Moreover, if circuit
descriptions for the relevant states are provided, we show that the task is
hard for the complexity class called (honest verifier) quantum statistical zero
knowledge via a reduction to a closely related result by Watrous.
