Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Abstract

We show that quantum states with “low stabilizer complexity” can be efficiently distinguished from Haar-random. Specifically, given an $n$-qubit pure state $|\psi ⟩$, we give an efficient algorithm that distinguishes whether $|\psi ⟩$ 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 $|\psi ⟩$, our algorithm uses $O(k^{12}\cdot \log (1/\delta ))$ copies of $|\psi ⟩$ and $O(n{k}^{12}\cdot \log (1/\delta ))$ time to succeed with probability at least $1-\delta$, and, with access to a state preparation unitary for $|\psi ⟩$ (and its inverse), $O(k^3\cdot \log (1/\delta ))$ queries and $O(n{k}^3\cdot \log (1/\delta ))$ time suffice. As a corollary, we prove that $\omega (\log (n))$ $T$-gates are necessary for any $\mathsf{Clifford}+T$ circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.