Let $\rho$ be a fixed, unknown $n$-qubit density matrix, and let $V$ be a fixed, known single-qubit unitary. Let $U = V \otimes V \otimes I_{n - 2}$, where $I_{n-2}$ is the identity on $n-2$ qubits, and let $\sigma = U \rho U^\dagger$. Furthermore, suppose that $\operatorname{Tr}(U\rho) = 0$. Let $$ F(\rho_1, \rho_2) = \left(\operatorname{Tr}\left(\sqrt{\sqrt{\rho_1}\rho_2\sqrt{\rho_1}}\right)\right)^2 $$ be the fidelity, where $\rho_1$ and $\rho_2$ are density matrices.
Suppose that we are guaranteed that either $F(\rho, \sigma) = 0$ (Scenario 1) or $F(\rho, \sigma) \geq \epsilon$ (Scenario 2). Given $N$ copies of $\rho$, what is the most sample-efficient protocol to determine which scenario we are in with probability at least $1-\delta$ of being correct?
By performing tomography, we can do this with a sample complexity that is exponential in $n$. Are there any protocols that only require polynomially many copies $N$? How hard should I expect this problem to be, e.g., is it at least as hard as some other task that is known to require exponentially many samples?
