Query-Optimal and Sample-Optimal Quantum Algorithms for Estimating Fidelity to a Pure State

We present two optimal quantum algorithms that estimate the (square root) fidelity of a mixed state to a pure state to within additive error $\varepsilon$:
- Given query access to the state-preparation circuits of the input states, the query complexity is shown to be $\Theta(1/\varepsilon)$, achieving a quadratic speedup over the folklore $O(1/\varepsilon^2)$.
- Given sample access to the input states, the sample complexity is shown to be $\Theta(1/\varepsilon^2)$, achieving a quadratic speedup over the folklore $O(1/\varepsilon^4)$.
Our results generalize the previous approaches to pure-state fidelity estimation, and, to the best of our knowledge, are the first optimal approaches to fidelity estimation involving mixed states. Our approach is technically simple, and can be extended to estimating the uncommon quantity $\sqrt{\operatorname{tr}(\rho\sigma^2)}$ that is of independent interest.