The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetilde{\Theta}(r^2/\varepsilon^2)$

Abstract:We settle the sample complexity of estimating the root Uhlmann fidelity $F(\rho,\sigma)=\operatorname{tr}\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}$ between an unknown state $\rho$ and a known rank-$r$ reference state $\sigma$. Writing $S(r,\varepsilon)$ for the sample complexity at additive error $\varepsilon$, we resolve the open problem posed by Wang by closing, up to logarithmic factors, the gap between the previously known bounds $\Omega(r/\varepsilon^2)$ and $O(r^2/\varepsilon^2)$. We prove $S(r,\varepsilon)=\widetilde{\Theta}(r^2/\varepsilon^2)$ for all $0<\varepsilon\le\varepsilon_0$, where $\varepsilon_0>0$ is a universal constant. The lower bound already holds on a $2r$-dimensional system when $\sigma$ is maximally mixed on a fixed $r$-dimensional subspace, and for a hard family of states that do not commute with $\sigma$. The proof combines exact spectral moment matching, a radially size-biased doubly correlated Wishart model, and the Cauchy identity, reducing state indistinguishability to a long-cycle estimate for a weighted random permutation. A direct-sum embedding and binomial thinning yield the optimal $1/\varepsilon^2$ dependence. We also prove a near-quadratic lower bound $\widetilde{\Omega}(r^2)$ for quantum spectrum estimation at constant accuracy. Combined with the recent $O(r^2(\log\log r/\log r)^2)$ upper bound, this determines the polynomial order of the sample complexity in this regime and establishes a near-quadratic barrier.

arXiv:2608.01770 [quant-ph]

(or arXiv:2608.01770v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.01770 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.