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:2507.14370

Affine Equivalence in the Clifford Hierarchy

Jonas T. Anderson, Andrew Connelly

Published Jul 18, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.14370

Related papers

Permutation gates in the third level of the Clifford hierarchy

Zhiyang He, Luke Robitaille, Xinyu Tan

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 $2^n$ 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$.

arXiv:2410.11818•Oct 15, 2024•1 citation

Semi-Cliffordness of the Clifford hierarchy for a single qudit in composite dimensions

Yifei Qi, Rahul Sarkar

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, \(\mathbb{Z}_d^2\) is a symplectic module rather than a vector space, motivating a distinction between four types of gates. Semi-Clifford gates ($\mathcal{SC}$) are the ones that become diagonal under left and right multiplication by Clifford gates, while a broader class $\mathcal{N}$ admits a permutation diagonal form, under left and right multiplication by Cliffords. Lagrangian semi-Clifford gates ($\mathcal{LSC}$) conjugate some maximal abelian Pauli subgroup to another, whereas generalized semi-Clifford gates ($\mathcal{GSC}$) map some maximal abelian Pauli subalgebra to another under conjugation. In square-free dimensions, we have \(\mathcal{SC}=\mathcal{LSC}\) and \(\mathcal{N}=\mathcal{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.

quant-pharXiv:2610.06836•Oct 6, 2026•0 citations

On Groups in the Qubit Clifford Hierarchy

Jonas T. Anderson

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.

arXiv:2212.05398•Quantum•Jun 13, 2024•12 citations

When is the Clifford hierarchy generalized semi-Clifford?

Rongbiao Thomas Wang, Bobby Zixuan Zhang

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 $\mathcal{C}_k(n)$ is semi-Clifford if and only if $k\le2$, $n\le2$, or $k=3$ and $n\le6$. We also establish that $\mathcal{C}_k(n)$ is generalized semi-Clifford when $k\le4$ or $n\le3$ and construct counterexamples when $k,n \geq 5$. For $n=4$ and $k\ge5$, we show that every gate defined over $\mathbb{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 $\mathcal{C}_k(n)$ is generalized semi-Clifford if and only if $k\le4$ or $n\le4$. Lastly, we go beyond this structure by introducing $n_c$-generalized semi-Clifford gates, which we show are exactly the gates of the form $\sum_x|π(x)\rangle\langle x|\otimes V_x$ up to Clifford gates on both sides, where $π$ permutes the computational basis states of $n_c$ control qubits. We conjecture that for $k\ge3$ every gate in $\mathcal{C}_k(n)$ has this form for some $n_c\ge1$ with every $V_x\in\mathcal{C}_{k-3}(n-n_c)$, refining the conjecture of Zeng, Chen, and Chuang.

quant-pharXiv:2610.06402•Oct 6, 2026•0 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

Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy

Zhiyang He, Luke Robitaille, Xinyu Tan

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\geq 3}$ in staircase form such that each $U_k$ is in the third level but its inverse is not in the $k$-th level.

arXiv:2510.04993•Leibniz international proceedings in informatics•Oct 6, 2025•0 citations
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.
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 2n2^n2n 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 777.
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 ddd is semi-Clifford, if and only if ddd is square-free. In composite dimensions, Zd2\mathbb{Z}_d^2Zd2​ is a symplectic module rather than a vector space, motivating a distinction between four types of gates. Semi-Clifford gates (SC\mathcal{SC}SC) are the ones that become diagonal under left and right multiplication by Clifford gates, while a broader class N\mathcal{N}N admits a permutation diagonal form, under left and right multiplication by Cliffords. Lagrangian semi-Clifford gates (LSC\mathcal{LSC}LSC) conjugate some maximal abelian Pauli subgroup to another, whereas generalized semi-Clifford gates (GSC\mathcal{GSC}GSC) map some maximal abelian Pauli subalgebra to another under conjugation. In square-free dimensions, we have SC=LSC\mathcal{SC}=\mathcal{LSC}SC=LSC and N=GSC\mathcal{N}=\mathcal{GSC}N=GSC, but when ddd 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.
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.
We study semi-Clifford and generalized semi-Clifford structures in the Clifford hierarchy as a function of hierarchy level kkk and qubit number nnn. We show that Ck(n)\mathcal{C}_k(n)Ck​(n) is semi-Clifford if and only if k≤2k\le2k≤2, n≤2n\le2n≤2, or k=3k=3k=3 and n≤6n\le6n≤6. We also establish that Ck(n)\mathcal{C}_k(n)Ck​(n) is generalized semi-Clifford when k≤4k\le4k≤4 or n≤3n\le3n≤3 and construct counterexamples when k,n≥5k,n \geq 5k,n≥5. For n=4n=4n=4 and k≥5k\ge5k≥5, we show that every gate defined over Q(i)\mathbb{Q}(i)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)\mathcal{C}_k(n)Ck​(n) is generalized semi-Clifford if and only if k≤4k\le4k≤4 or n≤4n\le4n≤4. Lastly, we go beyond this structure by introducing ncn_cnc​-generalized semi-Clifford gates, which we show are exactly the gates of the form ∑x∣π(x)⟩⟨x∣⊗Vx\sum_x|π(x)\rangle\langle x|\otimes V_x∑x​∣π(x)⟩⟨x∣⊗Vx​ up to Clifford gates on both sides, where πππ permutes the computational basis states of ncn_cnc​ control qubits. We conjecture that for k≥3k\ge3k≥3 every gate in Ck(n)\mathcal{C}_k(n)Ck​(n) has this form for some nc≥1n_c\ge1nc​≥1 with every Vx∈Ck−3(n−nc)V_x\in\mathcal{C}_{k-3}(n-n_c)Vx​∈Ck−3​(n−nc​), refining the conjecture of Zeng, Chen, and Chuang.
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 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 2n2^n2n 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 {Uk}k≥3\{U_k\}_{k\geq 3}{Uk​}k≥3​ in staircase form such that each UkU_kUk​ is in the third level but its inverse is not in the kkk-th level.