Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1608.06596 · Physical Review A

Diagonal gates in the Clifford hierarchy

Shawn Xingshan Cui, Daniel Gottesman, Anirudh Krishna

Published Jan 26, 2017• 73 citations
arXivHTMLPDF

Abstract

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 ${p}^{m}\mathrm{th}$ 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.

DOI
10.1103/physreva.95.012329

Related papers

Climbing the Clifford Hierarchy

Luca Bastioni, Samuel Glandon, Tefjol Pllaha +2 more

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.

quant-pharXiv:2603.12088•Mar 13, 2026•0 citations

The Clifford hierarchy for one qubit or qudit

Nadish de Silva, Oscar Lautsch

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.

arXiv:2501.07939•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 1, 2025•1 citation

The Generalized Semi-Clifford Conjecture Holds at Level 4

Maxwell Marcus, Sathyawageeswar Subramanian, Marcel Dall'Agnol

The Clifford hierarchy $\mathsf{C}_1 \subset \mathsf{C}_2 \subset \cdots$ 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 $\mathsf{C}_k$ 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 $\cup_k \mathsf{C}_k$ 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 \in \mathsf{C}_3$ on the span of maximal stabilizer subgroups (arXiv:2006.14040). By extending their fixed-point arguments to the group $Γ_1(U)$ generated by $U \mathsf{P} U^\dagger$ and beyond, we prove the conjecture for $k \leq 4$ and any prime dimension $d$. Our proof centers on conjugation groups $Γ_1(U), Γ_2(U), \ldots$ of $U \in \mathsf{C}_k$, 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.

quant-pharXiv:2609.38751•Oct 1, 2026•0 citations

Groups of diagonal gates in the Clifford hierarchy

Lingxuan Feng, Shunlong Luo

The Clifford hierarchy plays a crucial role in the stabilizer formalism of quantum error correction and quantum computation. Apart form the zeroth level (the discrete Heisenberg–Weyl group) and the first level (the Clifford group), all other levels of the Clifford hierarchy are not groups. However, the diagonal gates at all levels do form groups, and it is desirable to characterize their generators and structures. In this paper, we study the diagonal gates at the second level of the Clifford hierarchy. For this, we introduce the notion of a $$T$$ -gate in an arbitrary dimension, generalizing the corresponding notion in prime dimensions. By the use of the $$T$$ -gate, we are able to completely characterize the group structures of the diagonal gates at the second level of the Clifford hierarchy in any (not necessarily prime) dimension. It turns out that the classification depends crucially on the number-theoretic nature of the dimension. The results highlight the special role of the first two primes, $$2$$ and $$3$$ , in the prime factorization of the dimension. The $$T$$ -gate in an arbitrary dimension, apart from its key role as a generator of the diagonal gates, may have independent interest and further applications in quantum theory.

Theoretical and Mathematical Physics•Dec 1, 2024•5 citations

The generalised semi-Clifford conjecture is false

Nadish de Silva, Oscar Lautsch

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 importance of these gates has motivated numerous studies of their structure. Zeng-Chen-Chuang conjectured in 2007 that all hierarchy gates are generalised semi-Clifford, i.e. take the form $C_1 ΠD C_2$ for Clifford gates $C_1, C_2$, a permutation gate $Π$, and a diagonal gate $D$; Beigi-Shor proved in 2008 that this holds for all third-level gates. We construct a five-qubit gate that is in the fifth level of the Clifford hierarchy but is not generalised semi-Clifford. Rather than simply present and verify our counterexample to the generalised semi-Clifford conjecture, we show how its form can be deduced. Our counterexample also demonstrates that the Clifford hierarchy is not closed under inverses.

quant-pharXiv:2609.11903•Sep 11, 2026•0 citations

Unifying the Clifford hierarchy via symmetric matrices over rings

Narayanan Rengaswamy, Robert Calderbank, Henry D. Pfister

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 ${2}^{k}\mathrm{th}$ 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 $k\mathrm{th}$-level diagonal unitaries that can be described just by quadratic forms of the state over the ring ${\mathbb{Z}}_{{2}^{k}}$ of integers modulo ${2}^{k}$. The quadratic forms involve symmetric matrices over ${\mathbb{Z}}_{{2}^{k}}$ 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 ${\mathbb{Z}}_{{2}^{k}}$ 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 $\mathrm{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.

arXiv:1902.04022•Physical Review A•Aug 7, 2019•24 citations
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{p}^{m}\mathrm{th}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 mmm and the degree of the polynomial.
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 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 C1⊂C2⊂⋯\mathsf{C}_1 \subset \mathsf{C}_2 \subset \cdotsC1​⊂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\mathsf{C}_kCk​ for k>3k > 3k>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 ddd or with few qudits. The generalized semi-Clifford conjecture, proposed by Zeng et al. (arXiv:0712.2084), states that every gate in ∪kCk\cup_k \mathsf{C}_k∪k​Ck​ is, up to multiplication by Cliffords, the product of a permutation and a diagonal matrix. Beigi and Shor proved the case d=2d=2d=2, k=3k=3k=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∈C3U \in \mathsf{C}_3U∈C3​ on the span of maximal stabilizer subgroups (arXiv:2006.14040). By extending their fixed-point arguments to the group Γ1(U)Γ_1(U)Γ1​(U) generated by UPU†U \mathsf{P} U^\daggerUPU† and beyond, we prove the conjecture for k≤4k \leq 4k≤4 and any prime dimension ddd. Our proof centers on conjugation groups Γ1(U),Γ2(U),…Γ_1(U), Γ_2(U), \ldotsΓ1​(U),Γ2​(U),… of U∈CkU \in \mathsf{C}_kU∈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.
The Clifford hierarchy plays a crucial role in the stabilizer formalism of quantum error correction and quantum computation. Apart form the zeroth level (the discrete Heisenberg–Weyl group) and the first level (the Clifford group), all other levels of the Clifford hierarchy are not groups. However, the diagonal gates at all levels do form groups, and it is desirable to characterize their generators and structures. In this paper, we study the diagonal gates at the second level of the Clifford hierarchy. For this, we introduce the notion of a TTT -gate in an arbitrary dimension, generalizing the corresponding notion in prime dimensions. By the use of the TTT -gate, we are able to completely characterize the group structures of the diagonal gates at the second level of the Clifford hierarchy in any (not necessarily prime) dimension. It turns out that the classification depends crucially on the number-theoretic nature of the dimension. The results highlight the special role of the first two primes, 222 and 333 , in the prime factorization of the dimension. The TTT -gate in an arbitrary dimension, apart from its key role as a generator of the diagonal gates, may have independent interest and further applications in quantum theory.
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 importance of these gates has motivated numerous studies of their structure. Zeng-Chen-Chuang conjectured in 2007 that all hierarchy gates are generalised semi-Clifford, i.e. take the form C1ΠDC2C_1 ΠD C_2C1​ΠDC2​ for Clifford gates C1,C2C_1, C_2C1​,C2​, a permutation gate ΠΠΠ, and a diagonal gate DDD; Beigi-Shor proved in 2008 that this holds for all third-level gates. We construct a five-qubit gate that is in the fifth level of the Clifford hierarchy but is not generalised semi-Clifford. Rather than simply present and verify our counterexample to the generalised semi-Clifford conjecture, we show how its form can be deduced. Our counterexample also demonstrates that the Clifford hierarchy is not closed under inverses.
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{2}^{k}\mathrm{th}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 kkk and the degree of the polynomial. For qubit systems, we consider kthk\mathrm{th}kth-level diagonal unitaries that can be described just by quadratic forms of the state over the ring Z2k{\mathbb{Z}}_{{2}^{k}}Z2k​ of integers modulo 2k{2}^{k}2k. The quadratic forms involve symmetric matrices over Z2k{\mathbb{Z}}_{{2}^{k}}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{\mathbb{Z}}_{{2}^{k}}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\mathrm{Clifford}+TClifford+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.