# What are the relations between the permutation group and the Clifford group?

I'm trying to understand the relation between the permutation group on all the $$2^n$$ bitstrings and the Clifford group. My question arises from the fact that the Toffoli gate (which can be thought of as a permutation) cannot be decomposed in terms of Clifford operations. How do we prove it?

• Define the 3 qubit pauli group $G = <X_1,X_2,X_3,Z_1,Z_2,Z_3>$ then check that $T G T^\dagger \neq G$ so $T$ is not clifford Oct 18, 2022 at 20:48

I guess you're talking about unitaries which preserve computational basis states, i.e. which act as $$U|x\rangle = |f(x)\rangle$$ where $$f:\,\mathbb F_2^n \rightarrow \mathbb F_2^n$$ is a reversible Boolean function. These are exactly the permutations of bitstrings.

The only Clifford unitaries preserving computational basis states are those for which $$f$$ is an affine map. Thus the action is $$U_{A,b}|x\rangle = |A x + b\rangle$$ for some invertible matrix $$A\in\mathrm{Gl}(n,\mathbb F_2)$$ and a vector $$b\in\mathbb F_2^n$$. It is easy to show that the linear part of the transformation is generated by CNOT gates, while the affine shift can be realized with $$X$$ gates. Now, Toffoli fixes $$|0\rangle$$, hence if it would be Clifford, then it would have to be realized by a linear map (i.e. one for which the affine shift is $$b=0$$.).

Finally, the Toffoli gate $$T$$ is not a linear map on bitstrings: $$T(1,1,1) = (1,1,0) \neq (1,0,0) + (0,1,1) = T(1,0,0) + T(0,1,1)$$. Thus $$T$$ is non-Clifford. In fact, the Toffoli gate is universal for classical reversible computation, i.e. every reversible circuit can be decomposed into Toffoli gates (using ancillary bits).

Remark: Of course, you can also check that the Toffoli gate is non-Clifford by letting it act on the generators of the Pauli group. Here, you find that the Toffoli gate maps Paulis to Cliffords, and is thus an element of the third level of the Clifford hierarchy.

• Could you please double check the equation? I don't see how it proves that $T$ is not a linear map on bitstrings. Nov 10, 2022 at 0:49
• @mavzolej you're right, the example was wrong. I corrected it. Nov 10, 2022 at 7:50
• Thanks, that really the most straightforward explanation by a counterexample. Nov 11, 2022 at 0:12
• The statement that $f$ is a linear map and the equation $U_A|x\rangle=|Ax\rangle$ imply that $|0\dots 0\rangle$ is necessarily a fixed point of every Clifford that preserves the computational basis states. I think that in general $f$ may be an affine map and its action on the computation basis is given by $U_{A,b}|x\rangle=|Ax+b\rangle$ for some $b\in\mathbb{F}_2^n$. A suitable counterexample is easily constructed from e.g. the Pauli $X$ gate. Feb 17, 2023 at 3:28
• @AdamZalcman Yes, the most general Clifford transformations are affine maps, and the affine shift comes from $X$ gates. They don't play a role here because Toffoli fixes 0. Anyway, the statement is missing that and should be corrected (which I will do in a second). Feb 17, 2023 at 13:52