Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

2025/06/30 by Fang, Wang, Wang, Qisheng · 4 citations
#FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2506.23650

Abstract

We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error ε by using Θ(1/ε) queries to their state-preparation circuits, achieving a quadratic speedup over the folklore O(1/ε²). Our approach is technically simple, and can moreover estimate the quantity √(tr(ρσ²)) that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.

Citations

• A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
• Mixed state tomography reduces to pure state tomography
• The debiased Keyl's algorithm: a new unbiased estimator for full state tomography
• Optimal lower bounds for quantum state tomography
• Conjugate queries can help
• Quantum algorithms for Uhlmann transformation
• Translating Between the Common Haar Random State Model and the Unitary Model
• Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
• Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
• On Estimating the Trace of Quantum State Powers
• On the sample complexity of purity and inner product estimation
• Quantum algorithms for matrix geometric means
• Local Test for Unitarily Invariant Properties of Bipartite Quantum States
• An invitation to the sample complexity of quantum hypothesis testing
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Quantum Lower Bounds by Sample-to-Query Lifting
• Improved Quantum Algorithms for Fidelity Estimation
• Testing matrix product states
• Sublinear quantum algorithms for estimating von Neumann entropy
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum Algorithms for Classical Probability Distributions
• Distributional property testing in a quantum world
• The Theory of Quantum Information
• Quantum state certification
• Efficient quantum tomography II
• Quantum Spectrum Testing
• Zero-knowledge against quantum attacks
• The quantum query complexity of approximating the median and related statistics
• Quantum Lower Bounds by Polynomials
• Cryptographic Distinguishability Measures for Quantum Mechanical States
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Statistical decision theory for quantum systems

Cited by

• A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
• High-Precision Fidelity Estimation with Common Randomized Measurements
• On Estimating the Quantum Tsallis Relative Entropy
• The Sample Complexity of Fidelity Estimation to a Known Rank-r Reference State Is \widetildeΘ(r²/ε²)

Related

• Improved Quantum Algorithms for Fidelity Estimation
• Efficient algorithm for fidelity estimation of two quantum states
• Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
• Quantum mean states are nicer than you think: fast algorithms to compute states maximizing average fidelity
• Learning the closest product state