The Clifford Hierarchy has been a central topic in quantum computation due to its strong connections with fault-tolerant quantum computation, magic state distillation, and more. Nevertheless, only sections of the hierarchy are fully understood, such as diagonal gates and third level gates. The diagonal part of the hierarchy can be climbed by taking square roots and adding controls. Similarly, square roots of Pauli gates (first level) are Clifford gates (climb to the second level). Based on this theme, we study gates whose square roots climb to the next level. In particular, we fully characterize Clifford gates whose square roots climb to the third level.
The Clifford hierarchy is a set of gates that appears in the theory of fault-tolerant quantum computation, but its precise structure remains elusive. We give a complete characterization of the diagonal gates in the Clifford hierarchy for prime-dimensional qudits. They turn out to be
pmth roots of unity raised to polynomial functions of the basis state to which they are applied, and we determine which level of the Clifford hierarchy a given gate sits in based on
m and the degree of the polynomial.
The Clifford hierarchy is a nested sequence of sets of quantum gates that can be fault-tolerantly performed using gate teleportation within standard quantum error correction schemes. The groups of Pauli and Clifford gates constitute the first and second ‘levels’, respectively. Non-Clifford gates from the third level or higher, such as the T gate, are necessary for achieving fault-tolerant universal quantum computation. Since it was defined 26 years ago by Gottesman–Chuang, two questions have been studied by numerous researchers. First, precisely which gates constitute the Clifford hierarchy? Second, which subset of the hierarchy gates admit efficient gate teleportation protocols? We completely solve both questions in the practically relevant case of the Clifford hierarchy for gates of one qubit or one qudit of prime dimension. We express every such hierarchy gate uniquely as a product of three simple gates, yielding also a formula for the size of every level. These results are a consequence of our finding that all such hierarchy gates can be expressed in a certain form that guarantees efficient gate teleportation. Our decomposition of Clifford gates as a unique product of three elementary Clifford gates is of broad applicability.
The Clifford hierarchy plays a central role in fault-tolerant quantum computation, but its higher levels remain only partially understood. Recent work on quantum higher order Fourier analysis characterizes membership in the Clifford hierarchy using quantum derivatives, but does not provide an explicit description of the individual levels. In this work, we address this problem by showing that the collection of quantum derivatives of a unitary operator forms a non-abelian
1-cocycle, and conversely that every such
1-cocycle arises from a unitary operator. This yields a recursive cohomological characterization of the Clifford hierarchy. We then specialize this framework to the third level and decompose the cocycle data into symplectic, affine, and phase components, each admitting a cohomological interpretation. As applications, we give a new proof that every two-qudit gate in the third level of the Clifford hierarchy is semi-Clifford, and prove for the first time that every three-qudit gate in the third level is semi-Clifford.
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 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.
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.