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$.

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

References in corpus (41)

• Quantum Computing in the NISQ era and beyond
• 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
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Quantum fingerprinting
• Quantum state tomography via compressed sensing
• On the Power of One Bit of Quantum Information
• Hamiltonian Simulation by Qubitization
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• On quantum Renyi entropies: a new generalization and some properties
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• Direct Fidelity Estimation from Few Pauli Measurements
• Training variational quantum algorithms is NP-hard
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Quantum speedup of Monte Carlo methods
• Practical characterization of quantum devices without tomography
• Simulation of topological field theories by quantum computers
• Creating superpositions that correspond to efficiently integrable probability distributions
• A quantum-inspired classical algorithm for recommendation systems
• Optimal Quantum Clocks
• Sample-optimal tomography of quantum states
• Toolbox for entanglement detection and fidelity estimation
• Quantum-inspired algorithms in practice
• Variational Quantum Fidelity Estimation
• Spin tomography
• Hamiltonian Simulation with Optimal Sample Complexity
• Quantum algorithm for Petz recovery channels and pretty good measurements
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Improvements in Quantum SDP-Solving with Applications
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Quantum algorithm for estimating Renyi entropies of quantum states
• A Survey of Quantum Property Testing
• Quantum algorithms for testing properties of distributions
• Variational quantum algorithms to estimate rank, quantum entropies, fidelity and Fisher information via purity minimization
• Improved Quantum Algorithms for Fidelity Estimation
• Fidelity-based supervised and unsupervised learning for binary classification of quantum states

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