  Clifford circuits -- i.e. circuits composed of only CNOT, Hadamard, and
$\pi/4$ phase gates -- play a central role in the study of quantum computation.
However, their computational power is limited: a well-known result of Gottesman
and Knill states that Clifford circuits are efficiently classically simulable.
We show that in contrast, "conjugated Clifford circuits" (CCCs) -- where one
additionally conjugates every qubit by the same one-qubit gate $U$ -- can
perform hard sampling tasks. In particular, we fully classify the computational
power of CCCs by showing that essentially any non-Clifford conjugating unitary
$U$ can give rise to sampling tasks which cannot be efficiently classically
simulated to constant multiplicative error, unless the polynomial hierarchy
collapses. Furthermore, by standard techniques, this hardness result can be
extended to allow for the more realistic model of constant additive error,
under a plausible complexity-theoretic conjecture. This work can be seen as
progress towards classifying the computational power of all restricted quantum
gate sets.
