Here we study the unitary groups that can be constructed using elements from the qubit Clifford Hierarchy. We first provide a necessary and sufficient canonical form that semi-Clifford and generalized semi-Clifford elements must satisfy to be in the Clifford Hierarchy. Then we classify the groups that can be formed from such elements. Up to Clifford conjugation, we classify all such groups that can be constructed using generalized semi-Clifford elements in the Clifford Hierarchy. We discuss a possible minor exception to this classification in the appendix. This may not be a full classification of all groups in the qubit Clifford Hierarchy as it is not currently known if all elements in the Clifford Hierarchy must be generalized semi-Clifford. In addition to the diagonal gate groups found by Cui et al., we show that many non-isomorphic (to the diagonal gate groups) generalized symmetric groups are also contained in the Clifford Hierarchy. Finally, as an application of this classification, we examine restrictions on transversal gates given by the structure of the groups enumerated herein which may be of independent interest.
Here we study the unitary groups that can be constructed using elements from the qubit Clifford Hierarchy. We first provide a necessary and sufficient canonical form that semi-Clifford and generalized semi-Clifford elements must satisfy to be in the Clifford Hierarchy. Then we classify the groups that can be formed from such elements. Up to Clifford conjugation, we classify all such groups that can be constructed using generalized semi-Clifford elements in the Clifford Hierarchy. We discuss a possible minor exception to this classification in the appendix. This may not be a full classification of all groups in the qubit Clifford Hierarchy as it is not currently known if all elements in the Clifford Hierarchy must be generalized semi-Clifford. In addition to the diagonal gate groups found by Cui et al., we show that many non-isomorphic (to the diagonal gate groups) generalized symmetric groups are also contained in the Clifford Hierarchy. Finally, as an application of this classification, we examine restrictions on transversal gates given by the structure of the groups enumerated herein which may be of independent interest.
In this paper we prove a collection of results on the structure of permutations in the Clifford Hierarchy. First, we leverage results from the cryptography literature on affine equivalence classes of 4-bit permutations which we use to find all 4-qubit permutations in the Clifford Hierarchy. We then use the classification of 4-qubit permutations and previous results on the structure of diagonal gates in the Clifford Hierarchy to prove that all 4-qubit gates in the third level of the Clifford Hierarchy are semi-Clifford. Finally, we introduce the formalism of cycle structures to permutations in the Clifford Hierarchy and prove a general structure theorem about them. We also classify many small cycle structures up to affine equivalence. Interestingly, this classification is independent of the number of qubits.
We study semi-Clifford and generalized semi-Clifford structures in the Clifford hierarchy as a function of hierarchy level k and qubit number n. We show that Ck(n) is semi-Clifford if and only if k≤2, n≤2, or k=3 and n≤6. We also establish that Ck(n) is generalized semi-Clifford when k≤4 or n≤3 and construct counterexamples when k,n≥5. For n=4 and k≥5, we show that every gate defined over Q(i) up to a scalar is generalized semi-Clifford, reduce the general case to a single level, and propose a strategy to prove our conjecture that Ck(n) is generalized semi-Clifford if and only if k≤4 or n≤4. Lastly, we go beyond this structure by introducing nc-generalized semi-Clifford gates, which we show are exactly the gates of the form ∑x∣π(x)⟩⟨x∣⊗Vx up to Clifford gates on both sides, where π permutes the computational basis states of nc control qubits. We conjecture that for k≥3 every gate in Ck(n) has this form for some nc≥1 with every Vx∈Ck−3(n−nc), refining the conjecture of Zeng, Chen, and Chuang.
The Clifford hierarchy is a fundamental structure in quantum computation, classifying unitary operators based on their commutation relations with the Pauli group. Despite its significance, the mathematical structure of the hierarchy is not well understood at the third level and higher. In this work, we study permutations in the hierarchy: gates which permute the 2n basis states. We fully characterize all the semi-Clifford permutation gates. Moreover, we prove that any permutation gate in the third level, not necessarily semi-Clifford, must be a product of Toffoli gates in what we define as staircase form, up to left and right multiplications of Clifford permutations. Finally, we show that the smallest number of qubits for which there exists a non-semi-Clifford permutation in the third level is 7.
The Clifford hierarchy C1⊂C2⊂⋯ was introduced by Gottesman and Chuang (arXiv:quant-ph/9908010) to characterize gates that admit fault-tolerant implementation by gate teleportation. Yet, despite its rich mathematical structure and the attention it has received in recent years, little is known about Ck for k>3. Most progress has focused on identifying structural properties of restrictions of the hierarchy, such as diagonal gates and gates on systems of small dimension d or with few qudits.
The generalized semi-Clifford conjecture, proposed by Zeng et al. (arXiv:0712.2084), states that every gate in ∪kCk is, up to multiplication by Cliffords, the product of a permutation and a diagonal matrix. Beigi and Shor proved the case d=2, k=3 (arXiv:0810.5108) and Pllaha et al. found an alternative proof by exploiting fixed points of the conjugation map induced by (a Clifford correction of) U∈C3 on the span of maximal stabilizer subgroups (arXiv:2006.14040). By extending their fixed-point arguments to the group Γ1(U) generated by UPU† and beyond, we prove the conjecture for k≤4 and any prime dimension d.
Our proof centers on conjugation groups Γ1(U),Γ2(U),… of U∈Ck, which we expect to be a useful tool in the study of the Clifford hierarchy more generally. We also show a natural sufficient condition on such groups for gates in higher levels to be generalized semi-Clifford.
An important question in quantum information theory asks whether every gate in the Clifford hierarchy is semi-Clifford or not, as such gates admit resource-efficient implementations via gate teleportation. Extending recent results for prime dimensions~\cite{silva_clifford_2025}, we prove that every hierarchy gate on a single qudit of dimension d is semi-Clifford, if and only if d is square-free. In composite dimensions, Zd2 is a symplectic module rather than a vector space, motivating a distinction between four types of gates. Semi-Clifford gates (SC) are the ones that become diagonal under left and right multiplication by Clifford gates, while a broader class N admits a permutation diagonal form, under left and right multiplication by Cliffords. Lagrangian semi-Clifford gates (LSC) conjugate some maximal abelian Pauli subgroup to another, whereas generalized semi-Clifford gates (GSC) map some maximal abelian Pauli subalgebra to another under conjugation. In square-free dimensions, we have SC=LSC and N=GSC, but when d is not square-free, these equivalences can fail, as Lagrangian submodules can become non-free. We also show that every third-level gate of the one-qudit Clifford hierarchy is a generalized semi-Clifford in arbitrary dimensions.
The Clifford hierarchy of unitary operators is a foundational concept for universal quantum computation. It was introduced to show that universal quantum computation can be realized via quantum teleportation, given access to certain standard resources. While the full structure of the hierarchy is still not understood, Cui et al. [S. X. Cui et al., Phys. Rev. A 95, 012329 (2017)] recently described the structure of diagonal unitaries in the hierarchy. They considered diagonal unitaries whose action on a computational basis qudit state is described by a 2kth root of unity raised to some polynomial function of the state, and they established the level of such unitaries in the hierarchy as a function of k and the degree of the polynomial. For qubit systems, we consider kth-level diagonal unitaries that can be described just by quadratic forms of the state over the ring Z2k of integers modulo 2k. The quadratic forms involve symmetric matrices over Z2k that can be used to efficiently describe all two-local and certain higher locality diagonal gates in the hierarchy. We also provide explicit algebraic descriptions of their action on Pauli matrices, which establishes a natural recursion to diagonal unitaries from lower levels. The result involves symplectic matrices over Z2k and hence our perspective unifies a subgroup of diagonal gates in the Clifford hierarchy with the binary symplectic framework for gates in the Clifford group. We augment our description with simple examples for certain standard gates. In addition to demonstrating structure, these formulas might prove useful in applications such as (i) classical simulation of quantum circuits, especially via the stabilizer rank approach, (ii) synthesis of logical non-Clifford unitaries, specifically alternatives to expensive magic state distillation, and (iii) decomposition of arbitrary unitaries beyond the Clifford+T set of gates, perhaps leading to shorter depth circuits. Our results suggest that some nondiagonal gates in the hierarchy might also be understood by generalizing other binary symplectic matrices to integer rings.