Estimating Fidelity to a Reference Quantum State

Abstract

We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\epsilon$. We show that the sample complexity is $O(r^2/{\epsilon }^2)$ with optimal $\epsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2{\log }^2(1/\epsilon )/{\epsilon }^4)$ due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of $\hat{I}\text{c◯}(r/{\epsilon }^2)$, improving the previous best $\hat{I}\text{c◯}(r/\epsilon +1/{\epsilon }^2)$, with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most $r$ while the reference state can be arbitrary, for which the sample complexity is shown to be $O(r^2/{\epsilon }^4)$. As an application, we present an approach to tolerant quantum state certification, generalizing the exact certification studied in Bădescu, O'Donnell, and Wright (STOC 2019).

20 pages, 1 table, 1 figure, 4 algorithms