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.

31 pages, 2 figures, 2 algorithms

References in corpus (14)

• Entanglement detection
• Quantum random access memory
• Direct Fidelity Estimation from Few Pauli Measurements
• Quantum state discrimination and its applications
• Subsystem Trace Distance in Quantum Field Theory
• 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
• Fast Quantum Algorithms for Trace Distance Estimation
• Improved Quantum Algorithms for Fidelity Estimation
• Trace distance between fermionic Gaussian states from a truncation method
• Space-bounded quantum state testing via space-efficient quantum singular value transformation
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions

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