Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer

We settle the problem of estimating the trace distance and (square root) fidelity between $n$-qubit pure quantum states to within additive error $\varepsilon$, given their independent samples, which was raised as an open question by Wang (IEEE Trans.

Inf.

Theory 2024).

This is achieved by a quantum algorithm with optimal sample complexity $\Theta(1/\varepsilon^2)$, improving the long-standing folklore with sample complexity $O(1/\varepsilon^4)$.

At the heart of our algorithm is a samplized phase estimation of the product of two Householder reflections.

This is realized by an improved (multi-)samplizer for pure states, through which any quantum query algorithm using $Q$ queries to the reflection operator $I - 2|\psi\rangle\!\langle\psi|$ can be converted to a $\delta$-close (in the diamond norm distance) quantum sample algorithm using $\Theta(Q^2/\delta)$ samples of the state $|\psi\rangle$.

This samplizer for pure states is also shown to be optimal.