Institute of Information Science, Academia Sinica

We establish connections between state tomography, pseudorandomness, state synthesis lower bounds, and classical circuit lower bounds. In particular, let C be a class of quantum states that can be prepared by a non-uniform family of poly-size quantum circuits. We show that if there exists an algorithm that, given copies of a quantum state, distinguishes whether it is in C or is Haar random, promised one of these is the case, that uses at most O(2^{n^2}) time and 2^{n^{0.99}} samples then stateBQE is not a subset of stateC. Here stateBQE = stateBQTIME[2^{O(n)}] and stateC are state synthesis complexity classes as introduced by (Rosenthal and Yuen 2022), which capture problems with classical inputs but quantum output. We prove formally that efficient tomography implies an efficient distinguishing algorithm, so the ability to do sufficiently fast tomography also implies state synthesis lower bounds for C. Finally, combined with a result from (Rosenthal 2024), our result says that an O(2^{n^2})-time and 2^{n^{0.99}}-sample algorithm that distinguishes QAC^0_f states from Haar random implies EXP is not a subset of TC^0, which would be a monumental breakthrough in classical circuit complexity. This help sheds light on why time-efficient learning algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results in (Arunachalam, Grilo, Gur, Oliveira, and Sundaram 2022) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes. For instance, just as they constructed a novel conditional pseudorandom generator secure against uniform sub-exponential-time quantum computations, we likewise construct a conditional pseudorandom state (ensemble) that is secure against uniform sub-exponential-time quantum computation and which relies on the complexity theoretic assumption that PSPACE is not a subset of BQSUBEXP. We also establish circuit size hierarchy theorems for non-uniform state synthesis and connections between state synthesis class separations and decision class separations, which may be of independent interest.