Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank
The paper estimates how many samples are needed to accurately determine if a quantum state is close to a known reference state of rank-r. It shows that this sample complexity scales as $\Theta(e r^2/\epsilon^2)$, closing a gap between previous bounds. This result applies to both fidelity estimation and quantum spectrum estimation, proving the required samples are nearly quadratic in the rank.