Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error $\epsilon$ by using $\mathrm{\Theta }(1\mathrm{/}\epsilon )$ queries to their state-preparation circuits, achieving a quadratic speedup over the folklore $O(1\mathrm{/}{\epsilon }^2)$. Our approach is technically simple, and can moreover estimate the quantity $\sqrt{\mathrm{tr}(\rho {\sigma }^2)}$ that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.