Characterization of permutation gates in the third level of the Clifford hierarchy

Abstract

The Clifford hierarchy is a fundamental structure in quantum computation whose mathematical properties are not fully understood. In this work, we characterize permutation gates -- unitaries which permute the $2^n$ basis states -- in the third level of the hierarchy. We prove that any permutation gate in the third level must be a product of Toffoli gates in what we define as \emph{staircase form}, up to left and right multiplications by Clifford permutations. We then present necessary and sufficient conditions for a staircase form permutation gate to be in the third level of the Clifford hierarchy. As a corollary, we construct a family of non-semi-Clifford permutation gates $\{U_k{\}}_{k\ge 3}$ in staircase form such that each $U_k$ is in the third level but its inverse is not in the $k$-th level.

Supersedes arXiv:2410.11818, which established only a necessary but not sufficient condition for a permutation gate to lie in the third level of the Clifford hierarchy, and did not include the gates $U_k$ described in the abstract of the present paper