Vishnu Iyer, University of Texas Austin
We show that quantum states with “low stabilizer complexity” can be efficiently distinguished from Haar-random. Specifically, given an $n$-qubit pure state $\lvert \psi \rangle$, we give an efficient algorithm that distinguishes whether $\lvert \psi \rangle$ is (i) Haar-random or (ii) a state with stabilizer fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$ with some stabilizer state), promised that one of these is the case. With black-box access to $\lvert \psi \rangle$, our algorithm uses $O \big( k^{12} \cdot \log(1/\delta) \big)$ copies of $\lvert \psi \rangle$ and $O\big( nk^{12} \cdot \log (1/\delta) \big)$ time to succeed with probability at least $1 - \delta$, and, with access to a state preparation unitary for $\lvert \psi \rangle$ (and its inverse), $O\big( k^{3} \cdot \log(1/\delta) \big)$ queries and $O(nk^{3} \cdot \log(1/ \delta) \big)$ time suffice. As a corollary, we prove that $\omega\big( \log(n) \big)$ $T$-gates are necessary for any $\mathsf{Clifford} + T$ circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.
Join via Zoom