Background from Is there a closure property for the entire Clifford hierarchy? : The Clifford hierarchy (on $n$ qubits), is a collection of nested subsets $\mathcal C^{(1)} \subset \mathcal C^{(2)} \subset \mathcal C^{(3)} \subset \cdots \subset \mathbf U(2^n)$ of the unitary operators on $n$ qubits, defined recursively as follows:
$ \mathcal C^{(1)} $ is the Pauli group on $n$ qubits, i.e., the set of ($n$-fold tensor products of) Pauli operators with real or imaginary scalar factors: tensor products of $\{ \mathbf 1, X, Y, Z \}$ with a scalar factor of $\pm 1$ or $\pm i$.
For $k > 1$, we recursively define $\mathcal C^{(k)}$ as
$$ \mathcal C^{(k)} = \Bigl\{ U \in \mathbf U(2^n) \mathrel{\Big\vert} \forall P \in \mathcal C^{(1)} : U P U^\dagger \in \mathcal C^{(k-1)} \Bigr\}$$ — that is, the set of unitaries that, when used to conjugate a Pauli operator, yields an operator at one level lower in the hierarchy.
So, for example, the Clifford group is the second level of the Clifford hierarchy, $\mathcal C^{(2)}$, as any $U \in \mathcal C^{(2)}$ maps a Pauli operator to another Pauli operator (i.e., an element of $\mathcal C^{(1)}$) by conjugation.
The gates $ X,Z $ are in the Pauli group, the controlled gates $ CX,CZ $ are in the Clifford group. In general $ C^{r}X, C^{r}Z $ are in the $ r+1 $ level of the Clifford hierarchy. Similarly, the phase gate $ S $ is in the Clifford group and $ C^{r}S $ is in the $ r+2 $ level of the Clifford hierarchy.
Is it true that if $ U $ is a Clifford gate then controlled $ U $ is in the third level of the Clifford hierarchy? And in general is it true that the $ r $-controlled version of a Clifford gate will always be in the $ r+2 $ level of the Clifford hierarchy?
