# Which monomial matrices are in the Clifford hierarchy?

This is essentially a follow-up on the very interesting answer given here

Is there a closure property for the entire Clifford hierarchy?

I'm interested in sufficient conditions to conclude that a given gate is (or is not) in the Clifford hierarchy. I would be interested in any sort of "quick checks" I can put a matrix through to check whether or not it is in the Clifford hierarchy.

Along those lines:

The paper

https://arxiv.org/pdf/1608.06596.pdf

shows that a diagonal matrix in the $$k$$th level of the Clifford hierarchy must have all entries $$2^k$$ roots of unity.

Which monomial matrices are in the Clifford hierarchy?

$$\mathcal{C}^{(1)}$$ is the Pauli group and all elements of the Pauli group are monomial matrices. Thus the monomial matrices in the first level of the Clifford hierarchy are exactly all the Pauli matrices.

Lemma: Suppose that $$U,V$$ are unitaries such that $$U=VC$$ for some Clifford gate $$C$$. Then $$U \in \mathcal{C}^{(k)}$$ if and only if $$V \in \mathcal{C}^{(k)}$$.

Proof. $$U \in \mathcal{C}^{(k)}$$ iff $$UPU^{-1} \in \mathcal{C}^{(k-1)}$$ for all $$P \in \mathcal{C}^{(1)}$$ iff
$$(VC)P(VC)^{-1}=VCPC^{-1}V^{-1} \in \mathcal{C}^{(k-1)}$$ for all $$P \in \mathcal{C}^{(1)}$$ iff
$$VP'V^{-1} \in \mathcal{C}^{(k-1)}$$ for all $$P' \in \mathcal{C}^{(1)}$$ (recall conjugation by a Clifford gate is an automorphism of the Pauli group, by definition) which is true iff $$V \in \mathcal{C}^{(k)}$$

Recall that every monomial matrix $$M$$ can be written as $$M=DP$$ for $$D$$ a diagonal matrix and $$P$$ a permutation matrix (to get $$P$$ just replace all the nonzero entries of $$M$$ by $$1$$ and to get $$D$$ just take all the nonzero entries row by row and list them down the the diagonal).

So any monomial matrix whose corresponding permutation matrix $$P$$ is in the Clifford group and whose corresponding diagonal matrix $$D$$ is in the Clifford hierarchy will be in the Clifford hierarchy . And the diagonal matrix $$D$$ is in the Clifford hierarchy iff it has a certain form in terms of $$2^k$$ roots of unity see

https://arxiv.org/abs/1608.06596

unclear what kind of permutation matrices show up in the Clifford group/ Clifford hierarchy. For example Toffoli shows up in third level but not second level. Recall that Toffoli is $$CCX$$. So this is an example of the general fact that $$C^kX$$ is in the $$k+1$$ level of the Clifford hierarchy but not in the $$k$$ level of the Clifford hierarchy.

• For one and two qubits all permutations matrices are Clifford, but for three or more qubits there are non-Clifford permutations. An example of such a matrix is the non-Clifford Toffoli gate. Nov 9, 2022 at 21:07
• @JonasAnderson You are so right. I wonder if anyone has ever tried to characterize which permutation matrices are in the Clifford group? Or more generally in the Clifford hierarchy? Nov 9, 2022 at 21:08
• Pauli X strings and CNOTs generate the group of Clifford permutations (relative to the computational basis states). I have unpublished work on the subset (they do not form a group) of permutations in the Clifford Hierarchy. I list some rules they must follow but it seemed intractable generally. I exhaustively checked them all for n=3. I can send it to you if you like. Nov 9, 2022 at 21:17
• @JonasAnderson That would be lovely! My email is [email protected] Nov 9, 2022 at 23:03
• oh ya I just made typo yesterday when I wrote down $CNOT_{2,1}$ you're right I'm getting size $24$ now. I'll have to think more about the 2 qubit diagonal gates thing, maybe I'll ask a separate question May 4 at 13:05