Query-Optimal and Sample-Optimal Quantum Algorithms for Estimating Fidelity to a Pure State
This work provides the first optimal algorithms for fidelity estimation involving mixed states, addressing a fundamental problem in quantum information processing.
The authors present two quantum algorithms for estimating the square root fidelity between a mixed state and a pure state, achieving optimal query complexity Θ(1/ε) and sample complexity Θ(1/ε²), both quadratic improvements over previous folklore bounds.
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 $Θ(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 $Θ(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}(ρσ^2)}$ that is of independent interest.