Abstract
Stabilizer states, which are the outputs of Clifford circuits, play a central role in quantum information. They also have an efficient learning algorithm: Aaronson and Gottesman (2008) and Montanaro (2017) showed that n-qubit stabilizer states are learnable in poly(n) time. In this talk, I'll discuss recent joint works with Sabee Grewal, Vishnu Iyer, and Daniel Liang in which we give learning algorithms whose complexity scale with the "non-stabilizerness" in a quantum state. In particular, we prove new learnability and non-pseudorandomness results for outputs of Clifford+T circuits and states with bounded stabilizer fidelity.