Quantum State Learning Implies Circuit Lower Bounds

Nai-Hui Chia, Daniel Liang, Fang Song

We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let $\mathfrak{C}$ be a family of non-uniform…