Quantum State and Unitary Learning Implies Circuit Lower Bounds

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 quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of $\ket \psi$, distinguishes whether $\ket \psi$ is produced by $\mathfrak C$ or is Haar random, promised one of these is the case. For arbitrary fixed constant $c$, we show that if the algorithm uses at most $O\!\left(2^{n^c}\right)$ time and $2^{n^{0.99}}$ samples then $\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}$. Here $\mathsf{stateBQE} \coloneqq \mathsf{stateBQTIME}\left[2^{O(n)}\right]$ and $\mathsf{state}\mathfrak{C}$ are state synthesis complexity classes as introduced by Rosenthal and Yuen (2022), which capture problems with classical inputs but quantum output. Note that efficient tomography implies a similarly efficient distinguishing algorithm against Haar random states, even for nearly exponential-time algorithms. Because every state produced by a polynomial-size circuit can be learned with $2^{O(n)}$ samples and time, or $\omega(\mathrm{poly}(n))$ samples and $2^{\omega(\mathrm{poly}(n))}$ time, we show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis. Finally, a slight modification of our proof shows that distinguishing algorithms for quantum states can imply circuit lower bounds for decision problems as well. We then take these results and port them over to the setting of unitary learning and unitary synthesis. All combined, this helps shed light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work extends the results of Arunachalam et. al. (2022), which revealed a connection between quantum learning of \emph{Boolean functions} and circuit lower bounds for \emph{classical} circuit classes, to the setting of state (resp. unitary) tomography and state (resp. unitary) synthesis. As a result, we establish a conditional pseudorandom state (resp. unitary) generator, a circuit size hierarchy theorems for non-uniform state (resp. unitary) synthesis, and connections between state (resp. unitary) synthesis class separations and decision class separations, which may be of independent interest.