Daniel Liang

We show that any pseudoentangled state ensemble with a gap of t bits of entropy requires Ω(t) non-Clifford gates to prepare. This bound is tight up to polylogarithmic factors if linear-time quantum-secure pseudorandom functions exist. Our result follows from a polynomial-time algorithm to estimate the entanglement entropy of a quantum state across any cut of qubits. When run on an n-qubit state that is stabilized by at least 2^n−t Pauli operators, our algorithm produces an estimate that is within an additive factor of t/2 bits of the true entanglement entropy.

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^c) time and 2^n^0.99 samples then stateBQE⊄stateC. Here stateBQE:=stateBQTIME[2^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 2O(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.