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-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\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 $\varepsilon$.

arXiv:2610.04597 [quant-ph]

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

https://doi.org/10.48550/arXiv.2610.04597 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.