I want to sincerely thank my co-authors @mvscerezo.bsky.social, @dgarciamartin.bsky.social, Nahuel Diaz and, especially, the first author and main contributor of this paper Max West.

Given these were proposed to alleviate sample-complexity with respect to more-standard shadow protocols (which allow log-depth circuits), does this point at an underlying sample-complexity / circuit-depth trade-off?

These results have obvious implications for many proposed classical shadow tomography protocols, for example matchgate shadows (arxiv.org/abs/2207.13723): they require 'deep' (linear-depth) circuits.

In particular, we find (see table): no mixed-unitary one-designs, orthogonal/symplectic/matchgate 2-designs, and Clifford 8-designs can be achieved in sublinear depth with local gates. These findings imply many known (and some new) constructions are depth-optimal.

In this work, we derive general no-go theorems that rule out the existence of group designs with certain restrictions, e.g. depth or gate-count. Our results apply to a wide class of groups including the symplectic unitaries, matchgates, mixed-unitaries, Cliffords and other.

This question was originally raised in Schuster, Haferkamp and Huang's paper. They gave an argument ruling out short-depth designs for the orthogonal group and left it as an open question whether other groups, in particular if 'fermionic, bosonic, and Hamiltonian systems' would allow these as well.