Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank

Abstract

We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most $s$, we give an estimator using $O(s^2/\varepsilon^2)$ copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds $r,s$ as $\min\{r,s\}^2/\varepsilon^2$ up to logarithmic factors in the smaller rank. The same estimator gives the upper bound $O(r(\operatorname{tr}\sqrt{\sigma})^2/\varepsilon^2)$ for a rank-$r$ reference $\sigma$. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra $\lambda_i\propto i^{-\alpha}$ with fixed $1<\alpha\le2$, as $\varepsilon\downarrow0$ with $r\ge C_\alpha\varepsilon^{-2/(\alpha-1)}$, the bounds determine the complexity as $\widetilde\Theta_\alpha(\varepsilon^{-4/(\alpha-1)})$. In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.