Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Sabee Grewal, Vishnu Iyer, William Kretschmer +1

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…