Complexity Classification of Conjugated Clifford Circuits

Understand

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.