Optimal Trace Distance and Fidelity Estimations for Pure Quantum States

Abstract

Measuring the distinguishability between quantum states is a basic problem in quantum information theory. In this paper, we develop optimal quantum algorithms that estimate both the trace distance and the (square root) fidelity between pure states to within additive error $\epsilon$ using $\Theta (1/\epsilon )$ queries to their state-preparation circuits, quadratically improving the long-standing folklore $O(1/{\epsilon }^2)$. At the heart of our construction, is an algorithmic tool for quantum square root amplitude estimation, which generalizes the well-known quantum amplitude estimation.

arXiv comment31 pages, 2 figures, 2 algorithms

References in corpus (25)

• Entanglement detection
• Quantum Amplitude Amplification and Estimation
• Quantum fingerprinting
• Quantum random access memory
• Direct Fidelity Estimation from Few Pauli Measurements
• Quantum measurements and the Abelian Stabilizer Problem
• Quantum State Discrimination
• Quantum state discrimination and its applications
• Sample-optimal tomography of quantum states
• Quantum circuits cannot control unknown operations
• Variational Quantum Fidelity Estimation
• Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
• Subsystem Trace Distance in Quantum Field Theory
• Quantum Algorithm for Fidelity Estimation
• Quantum algorithms for testing properties of distributions
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Estimating distinguishability measures on quantum computers
• Distributed quantum inner product estimation
• Variational quantum algorithms to estimate rank, quantum entropies, fidelity and Fisher information via purity minimization
• Fast Quantum Algorithms for Trace Distance Estimation
• Improved Quantum Algorithms for Fidelity Estimation
• Trace distance between fermionic Gaussian states from a truncation method
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Space-bounded quantum state testing via space-efficient quantum singular value transformation

Cited by in corpus (3)

• Quantum algorithms for matrix geometric means
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Quantum Lower Bounds by Sample-to-Query Lifting