No-go theorems for sublinear-depth group designs

Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group $G$ possessing an invariant state $G^{\otimes k} \lvert\Psi\rangle= \lvert\Psi\rangle$, a lower bound on the diamond distance between the $k$\textsuperscript{th} moment operator of any ensemble of elements of $G$, and that of the Haar measure over $G$. We then use this bound to prove that for many groups of interest, no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$-design over $G$. More generally, on a $D$-dimensional lattice, our results imply that such group designs require depths scaling at least as $n^{1/D}$. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth $8$-designs over the Clifford group. 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.