Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an n-qubit pure state |psirangle, we give an efficient algorithm that distinguishes whether |psirangle is (i) Haar-random or (ii) a state with stabilizer fidelity at least frac1k (i.e., has fidelity at least frac1k with some stabilizer state), promised that one of these is the case. With black-box access to |psirangle, our algorithm uses O!left( k12 log(1/δ)right) copies of |psirangle and O!left(n k12 log(1/δ)right) time to succeed with probability at least 1-δ, and, with access to a state preparation unitary for |psirangle (and its inverse), O!left( k3 log(1/δ)right) queries and O!left(n k3 log(1/δ)right) time suffice. As a corollary, we prove that ω(log(n)) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.