Quantum Algorithm for Fidelity Estimation

摘要

For two unknown mixed quantum states $rho $ and $sigma $ in an $N$ -dimensional Hilbert space, computing their fidelity $F(rho,sigma)$ is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in ${mathrm{ poly}}(log (N), r, 1/varepsilon)$ time, where $r$ is the lower rank of $rho $ and $sigma $ , and $varepsilon $ is the desired precision, provided that the purifications of $rho $ and $sigma $ are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in $N$ .