No-go theorems for sublinear-depth group designs

Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a fundamental problem in quantum information theory, with breakthrough recent results showing that for the unitary group this can be achieved with depths scaling logarithmically in the system size. Here we prove that, for groups G possessing an invariant state $G^{\otimes k}\left(\Psi \right)=\left(\Psi \right)$ satisfying certain conditions on its entanglement structure, no subset of G consisting of sublinear-depth one-dimensional circuits with constant-locality gates can form an approximate k-design over G. More generally, on a D-dimensional lattice of side-length n, our results imply that such group designs require depths scaling at least as n^1/D. Among other examples, we show that there is a constant separation between the maximum depth and gate counts for which no circuit can approximate even the second moment of random matchgate circuits, and those required to implement the matchgate Haar distribution exactly. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over G using any circuit comprised of a sublinear number of gates generated by Pauli strings.