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.
How fast can quantum circuits compile group designs?Recent work arxiv.org/abs/2407.07754 showed that designs over the n-qubit unitary group can be compiled in logarithmic-in-n depth. Can we similarly build short-depth designs over other groups? In our new paper arxiv.org/abs/2506.16005 we answer no.
