Quantum Algorithm for Fidelity Estimation
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
For two unknown mixed quantum states <inline-formula> <tex-math notation="LaTeX">$\rho $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\sigma $ </tex-math></inline-formula> in an <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>-dimensional Hilbert space, computing their fidelity <inline-formula> <tex-math notation="LaTeX">$F(\rho,\sigma)$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">${\mathrm{ poly}}(\log (N), r, 1/\varepsilon)$ </tex-math></inline-formula> time, where <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> is the lower rank of <inline-formula> <tex-math notation="LaTeX">$\rho $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\sigma $ </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula> is the desired precision, provided that the purifications of <inline-formula> <tex-math notation="LaTeX">$\rho $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\sigma $ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>.