Daniel Liang

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.

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.