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:1902.04022 · Physical Review A

Unifying the Clifford hierarchy via symmetric matrices over rings

Narayanan Rengaswamy, Robert Calderbank, Henry D. Pfister

Published Aug 7, 2019• 24 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.100.022304

Related papers

Efficient quantum gate teleportation in higher dimensions

Nadish de Silva

The Clifford hierarchy is a nested sequence of sets of quantum gates critical to achieving fault-tolerant quantum computation. Diagonal gates of the Clifford hierarchy and ‘nearly diagonal’ semi-Clifford gates are particularly important: they admit efficient gate teleportation protocols that implement these gates with fewer ancillary quantum resources such as magic states. Despite the practical importance of these sets of gates, many questions about their structure remain open; this is especially true in the higher-dimensional qudit setting. Our contribution is to leverage the discrete Stone–von Neumann theorem and the symplectic formalism of qudit stabilizer theory towards extending the results of Zeng et al . (2008) and Beigi & Shor (2010) to higher dimensions in a uniform manner. We further give a simple algorithm for recursively enumerating all gates of the Clifford hierarchy, a simple algorithm for recognizing and diagonalizing semi-Clifford gates, and a concise proof of the classification of the diagonal Clifford hierarchy gates due to Cui et al . (2016) for the single-qudit case. We generalize the efficient gate teleportation protocols of semi-Clifford gates to the qudit setting and prove that every third-level gate of one qudit (of any prime dimension) and of two qutrits can be implemented efficiently. Numerical evidence gathered via the aforementioned algorithms supports the conjecture that higher-level gates can be implemented efficiently.

arXiv:2011.00127•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jul 1, 2021•16 citations

Un-Weyl-ing the Clifford Hierarchy

Tefjol Pllaha, Narayanan Rengaswamy, Olav Tirkkonen +1 more

The teleportation model of quantum computation introduced by Gottesman and Chuang (1999) motivated the development of the Clifford hierarchy. Despite its intrinsic value for quantum computing, the widespread use of magic state distillation, which is closely related to this model, emphasizes the importance of comprehending the hierarchy. There is currently a limited understanding of the structure of this hierarchy, apart from the case of diagonal unitaries (Cui et al., 2017; Rengaswamy et al. 2019). We explore the structure of the second and third levels of the hierarchy, the first level being the ubiquitous Pauli group, via the Weyl (i.e., Pauli) expansion of unitaries at these levels. In particular, we characterize the support of the standard Clifford operations on the Pauli group. Since conjugation of a Pauli by a third level unitary produces traceless Hermitian Cliffords, we characterize their Pauli support as well. Semi-Clifford unitaries are known to have ancilla savings in the teleportation model, and we explore their Pauli support via symplectic transvections. Finally, we show that, up to multiplication by a Clifford, every third level unitary commutes with at least one Pauli matrix. This can be used inductively to show that, up to a multiplication by a Clifford, every third level unitary is supported on a maximal commutative subgroup of the Pauli group. Additionally, it can be easily seen that the latter implies the generalized semi-Clifford conjecture, proven by Beigi and Shor (2010). We discuss potential applications in quantum error correction and the design of flag gadgets.

arXiv:2006.14040•Quantum•Dec 11, 2020•16 citations

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

Diagonal gates in the Clifford hierarchy

Shawn Xingshan Cui, Daniel Gottesman, Anirudh Krishna

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.

arXiv:1608.06596•Physical Review A•Jan 26, 2017•73 citations

A Cohomological Characterization of the Clifford Hierarchy

Junaid Aftab

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.

math-phCross-listedarXiv:2610.06699•Oct 6, 2026•0 citations

Clifford-hierarchy stabilizer formalism with applications to twisted quantum doubles

Christopher Fechisin, Kieran Cooney, Mathi Raja +4 more

Recent work has shown that quantum double models can be used to circumvent the Bravyi-Koenig bound. In particular, this is achieved through code-switching protocols in which non-Pauli stabilizer phases appear as intermediate codes. We introduce the $X\mathcal C^{(k)}_d$ stabilizer formalism, which generalizes the Pauli stabilizer formalism by combining Pauli-$X$ operators with diagonal operators drawn from a fixed level $k$ of the Clifford hierarchy on prime-dimensional qudits. This yields a natural class of beyond-Pauli stabilizer models, including many twisted quantum double phases. We classify a large class of these $X\mathcal C^{(k)}_d$ stabilizer states, showing that they are uniform superpositions over affine-linear subspaces with diagonal phases. In particular, when the stabilizers of a state require operators from level $k$ of the Clifford hierarchy, we show that the diagonal gates required to produce the phases in the wavefunction sit one level higher. We further show that every 2D twisted quantum double ${\cal D}^ω(\mathbb{Z}_p^n)$ with $ω$ a product of type-III cocycles and $p$ an odd prime admits a realization using only Clifford ($k=2$) stabilizers, and we conjecture that phases where $ω$ contains a type-I or type-II cocycle require level-$p$ Clifford-hierarchy stabilizers for $p$-dimensional qudits. Finally, we demonstrate that a pair of qudit toric codes may be deterministically prepared in a logical magic state by measuring $X\mathcal C^{(k)}_d$ stabilizers. Together, these results provide a concrete stabilizer framework for topological codes beyond Pauli stabilizer models and their logical gates.

quant-pharXiv:2610.00464•Oct 2, 2026•0 citations
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.
The Clifford hierarchy is a nested sequence of sets of quantum gates critical to achieving fault-tolerant quantum computation. Diagonal gates of the Clifford hierarchy and ‘nearly diagonal’ semi-Clifford gates are particularly important: they admit efficient gate teleportation protocols that implement these gates with fewer ancillary quantum resources such as magic states. Despite the practical importance of these sets of gates, many questions about their structure remain open; this is especially true in the higher-dimensional qudit setting. Our contribution is to leverage the discrete Stone–von Neumann theorem and the symplectic formalism of qudit stabilizer theory towards extending the results of Zeng et al . (2008) and Beigi & Shor (2010) to higher dimensions in a uniform manner. We further give a simple algorithm for recursively enumerating all gates of the Clifford hierarchy, a simple algorithm for recognizing and diagonalizing semi-Clifford gates, and a concise proof of the classification of the diagonal Clifford hierarchy gates due to Cui et al . (2016) for the single-qudit case. We generalize the efficient gate teleportation protocols of semi-Clifford gates to the qudit setting and prove that every third-level gate of one qudit (of any prime dimension) and of two qutrits can be implemented efficiently. Numerical evidence gathered via the aforementioned algorithms supports the conjecture that higher-level gates can be implemented efficiently.
The teleportation model of quantum computation introduced by Gottesman and Chuang (1999) motivated the development of the Clifford hierarchy. Despite its intrinsic value for quantum computing, the widespread use of magic state distillation, which is closely related to this model, emphasizes the importance of comprehending the hierarchy. There is currently a limited understanding of the structure of this hierarchy, apart from the case of diagonal unitaries (Cui et al., 2017; Rengaswamy et al. 2019). We explore the structure of the second and third levels of the hierarchy, the first level being the ubiquitous Pauli group, via the Weyl (i.e., Pauli) expansion of unitaries at these levels. In particular, we characterize the support of the standard Clifford operations on the Pauli group. Since conjugation of a Pauli by a third level unitary produces traceless Hermitian Cliffords, we characterize their Pauli support as well. Semi-Clifford unitaries are known to have ancilla savings in the teleportation model, and we explore their Pauli support via symplectic transvections. Finally, we show that, up to multiplication by a Clifford, every third level unitary commutes with at least one Pauli matrix. This can be used inductively to show that, up to a multiplication by a Clifford, every third level unitary is supported on a maximal commutative subgroup of the Pauli group. Additionally, it can be easily seen that the latter implies the generalized semi-Clifford conjecture, proven by Beigi and Shor (2010). We discuss potential applications in quantum error correction and the design of flag gadgets.
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.
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 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 111-cocycle, and conversely that every such 111-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.
Recent work has shown that quantum double models can be used to circumvent the Bravyi-Koenig bound. In particular, this is achieved through code-switching protocols in which non-Pauli stabilizer phases appear as intermediate codes. We introduce the XCd(k)X\mathcal C^{(k)}_dXCd(k)​ stabilizer formalism, which generalizes the Pauli stabilizer formalism by combining Pauli-XXX operators with diagonal operators drawn from a fixed level kkk of the Clifford hierarchy on prime-dimensional qudits. This yields a natural class of beyond-Pauli stabilizer models, including many twisted quantum double phases. We classify a large class of these XCd(k)X\mathcal C^{(k)}_dXCd(k)​ stabilizer states, showing that they are uniform superpositions over affine-linear subspaces with diagonal phases. In particular, when the stabilizers of a state require operators from level kkk of the Clifford hierarchy, we show that the diagonal gates required to produce the phases in the wavefunction sit one level higher. We further show that every 2D twisted quantum double Dω(Zpn){\cal D}^ω(\mathbb{Z}_p^n)Dω(Zpn​) with ωωω a product of type-III cocycles and ppp an odd prime admits a realization using only Clifford (k=2k=2k=2) stabilizers, and we conjecture that phases where ωωω contains a type-I or type-II cocycle require level-ppp Clifford-hierarchy stabilizers for ppp-dimensional qudits. Finally, we demonstrate that a pair of qudit toric codes may be deterministically prepared in a logical magic state by measuring XCd(k)X\mathcal C^{(k)}_dXCd(k)​ stabilizers. Together, these results provide a concrete stabilizer framework for topological codes beyond Pauli stabilizer models and their logical gates.