Quantum State Learning Implies Circuit Lower Bounds

We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let C be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of |, distinguishes whether | is produced by 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 (2^nᶜ) time and 2^n^{0. 99} samples then stateBQE stateC. Here stateBQE: = stateBQTIME2^O (n) and stateC are state synthesis complexity classes as introduced by Rosenthal and Yuen (ITCS 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 O (n^ (1) ) samples and 2^O (n^{ (1) ) } 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. This help sheds light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results by Arunachalam et al. (FOCS 2021) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes, but modified for the purposes of state tomography and state synthesis.