Efficient Quantum State Identity Testing

Abstract

We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\epsilon$ or some pair has fidelity at most $\epsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\epsilon \in (0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log (n/\delta )\log (2/\delta ))$ copies of each input state to succeed with probability at least $1-\delta$. The second uses the Schur transform to reduce the sample complexity to $O(\log (n/\delta ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $\Omega (\log (n/\delta ))$ for any quantum algorithm with failure probability at most $\delta \le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $\delta$ for fixed $\epsilon$.

24 pages