Unitary Subgroup Testing

We consider the problem of $\textit{subgroup testing}$ for a quantum circuit $C$: given access to $C$, determine whether it implements a unitary from a subgroup $\mathcal{G}$ of the unitary group. In particular, the group $\mathcal{G}$ can be the trivial subgroup (i.e., identity testing) or groups such as the Pauli or Clifford groups, or even their $q$-ary extensions. We also consider a $\textit{promise}$ version of the problem where $C$ is promised to be in some subgroup of the unitaries that contains $\mathcal{G}$ (e.g., identity testing for Clifford circuits). We present a novel structural property of Clifford unitaries. Namely, that their (normalized) trace is bounded by $1/\sqrt{2}$ in absolute value, regardless of the dimension. We show a similar property for the $q$-ary Cliffords. This allows us to analyze a very simple single-query identity test under the Clifford promise and show that it has (at least) constant soundness. The same test has perfect soundness under the Pauli promise. We use the test to show that identity/Pauli/Clifford testing (without promise) are all computationally equivalent, thus establishing computational hardness for Pauli and Clifford testing.