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

Abstract

We settle the problem of estimating the trace distance and (square root) fidelity between $n$-qubit pure quantum states to within additive error $\epsilon$, 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 $\hat{I}˜(1/{\epsilon }^2)$, improving the long-standing folklore with sample complexity $O(1/{\epsilon }^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|\ddot{I}ˆ⟩⟨\ddot{I}ˆ|$ can be converted to a $\hat{I}´$-close (in the diamond norm distance) quantum sample algorithm using $\hat{I}˜(Q^2/\hat{I}´)$ samples of the state $|\ddot{I}ˆ⟩$. This samplizer for pure states is also shown to be optimal.

25 pages, 3 figures, 1 table, 1 algorithm. Full version of the conference version. Minor modifications