Quantum Algorithm for Fidelity Estimation

Abstract

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/\epsilon )$ time, where $r$ is the lower rank of $\rho$ and $\sigma$, and $\epsilon$ 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$.

Final version with an improvement over the previous version. 19 pages, 2 tables, 1 algorithm

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Entanglement detection
• Entanglement Spectrum as a Generalization of Entanglement Entropy: Identification of Topological Order in Non-Abelian Fractional Quantum Hall Effect States
• Direct Fidelity Estimation from Few Pauli Measurements
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Creating superpositions that correspond to efficiently integrable probability distributions
• Toolbox for entanglement detection and fidelity estimation
• Variational quantum algorithms to estimate rank, quantum entropies, fidelity and Fisher information via purity minimization
• Improved Quantum Algorithms for Fidelity Estimation

Cited by in corpus (19)

• Estimating distinguishability measures on quantum computers
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Multivariate trace estimation in constant quantum depth
• Fast Quantum Algorithms for Trace Distance Estimation
• Quantum Neural Estimation of Entropies
• Swap Test-based Characterization of Quantum Processes in Universal Quantum Computers
• Noise-adapted recovery circuits for quantum error correction
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
• Quantum algorithms for matrix geometric means
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Efficient fidelity estimation: Alternative derivation and related applications
• Operation fidelity explored by numerical range of Kraus operators
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Quantum Lower Bounds by Sample-to-Query Lifting
• Q-fid: Quantum Circuit Fidelity Improvement with LSTM Networks
• Disentangling quantum neural networks for unified estimation of quantum entropies and distance measures
• Performance Guarantees for Quantum Neural Estimation of Entropies