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

The Clifford Hierarchy as Group Cohomology: TWIST as the Schur Multiplier Certificate

Ian Richard C Buckley

Published Jul 6, 2026• 0 citations
Publisher

Abstract

The Clifford hierarchy $\mathsf{C}_1 \subset \mathsf{C}_2 \subset \mathsf{C}_3 \subset \cdots$ is usually defined inductively: a gate $U$ is at level $k+1$ if it maps every Pauli to level $k$ under conjugation. This paper shows that this definition is the shadow of a cohomological statement: the boundary between $\mathsf{C}_2$ (Clifford) and $\mathsf{C}_3$ (magic) is witnessed by a non-trivial element of $H^2(\mathrm{Sp}(4,\mathbb{F}_2);\mathbb{Z}_2)$, the obstruction to lifting a projective representation of the symplectic group to a genuine one. The T gate is the canonical representative of this non-trivial class. The obstruction is proved computationally for $\mathrm{Sp}(4,\mathbb{F}_2)$ via the Weil representation: for any BFS-lifted section $g \mapsto W_g$, there exist elements $g$ of Sp-order $d$ for which $W_g^d = -I$ (not $+I$), directly witnessing the $\mathbb{Z}_2$ obstruction. Sixty-seven such witnesses are found; the simplest has Sp-order 2 with Clifford lift of order 4. The TWIST opcode in the Origami ISA counts the number of times this cohomology class is "charged" in a circuit. TWIST $= 0$ is equivalent to the circuit lying in the trivial $\mathbb{Z}_2$ class, and hence to Gottesman-Knill classical simulability. This makes the Schur multiplier $\mathbb{Z}_2$ a computable certificate for quantum advantage. The paper unifies three apparently distinct $\mathbb{Z}2$ obstructions: (1) the Schur multiplier of $\mathrm{Sp}(4,\mathbb{F}2)$, witnessed by the T gate; (2) Pauli anti-commutation, $XZ = -ZX$; (3) the SPT invariant of the cluster state, whose virtual bond symmetry satisfies $(U{g_x} U{g_z})(U_{g_z} U_{g_x})^{-1} = -I \in H^2(\mathbb{Z}_2 \times \mathbb{Z}_2; U(1)) = \mathbb{Z}_2$. These are shown to be three languages for one object, related by explicit inflation and restriction maps. Keywords Clifford hierarchy, group cohomology, Schur multiplier, symplectic group, metaplectic representation, Weil representation, T gate, magic states, quantum advantage, Gottesman-Knill theorem, symmetry-protected topological phases, cluster state, Origami ISA, TWIST opcode, $H^2$ obstruction

DOI
10.5281/zenodo.21219712

Related papers

The Clifford Hierarchy as Group Cohomology: TWIST as the Schur Multiplier Certificate

Ian Richard C Buckley

The Clifford hierarchy $\mathsf{C}_1 \subset \mathsf{C}_2 \subset \mathsf{C}_3 \subset \cdots$ is usually defined inductively: a gate $U$ is at level $k+1$ if it maps every Pauli to level $k$ under conjugation. This paper shows that this definition is the shadow of a cohomological statement: the boundary between $\mathsf{C}_2$ (Clifford) and $\mathsf{C}_3$ (magic) is witnessed by a non-trivial element of $H^2(\mathrm{Sp}(4,\mathbb{F}_2);\mathbb{Z}_2)$, the obstruction to lifting a projective representation of the symplectic group to a genuine one. The T gate is the canonical representative of this non-trivial class. The obstruction is proved computationally for $\mathrm{Sp}(4,\mathbb{F}_2)$ via the Weil representation: for any BFS-lifted section $g \mapsto W_g$, there exist elements $g$ of Sp-order $d$ for which $W_g^d = -I$ (not $+I$), directly witnessing the $\mathbb{Z}_2$ obstruction. Sixty-seven such witnesses are found; the simplest has Sp-order 2 with Clifford lift of order 4. The TWIST opcode in the Origami ISA counts the number of times this cohomology class is "charged" in a circuit. TWIST $= 0$ is equivalent to the circuit lying in the trivial $\mathbb{Z}_2$ class, and hence to Gottesman-Knill classical simulability. This makes the Schur multiplier $\mathbb{Z}_2$ a computable certificate for quantum advantage. The paper unifies three apparently distinct $\mathbb{Z}2$ obstructions: (1) the Schur multiplier of $\mathrm{Sp}(4,\mathbb{F}2)$, witnessed by the T gate; (2) Pauli anti-commutation, $XZ = -ZX$; (3) the SPT invariant of the cluster state, whose virtual bond symmetry satisfies $(U{g_x} U{g_z})(U_{g_z} U_{g_x})^{-1} = -I \in H^2(\mathbb{Z}_2 \times \mathbb{Z}_2; U(1)) = \mathbb{Z}_2$. These are shown to be three languages for one object, related by explicit inflation and restriction maps. Keywords Clifford hierarchy, group cohomology, Schur multiplier, symplectic group, metaplectic representation, Weil representation, T gate, magic states, quantum advantage, Gottesman-Knill theorem, symmetry-protected topological phases, cluster state, Origami ISA, TWIST opcode, $H^2$ obstruction

•Jul 3, 2026•0 citations

Generalized Clifford groups and simulation of associated quantum circuits

Stephen R. L. Clark, Richard Jozsa, Noah Linden

Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup $G$ of $U(d)$. In particular we seek $G$ such that $G\otimes G$ has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case $d = 2$ we exhaustively treat all finite irreducible subgroups of $U(2)$ and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the $n^{\rm th}$ root of $Z$ for $n \in \N$.

Quantum Information and Computation•Jan 1, 2008•22 citations

Clifford Hierarchy Stabilizer Codes: Transversal Non-Clifford Gates and Magic

Ryohei Kobayashi, Guanyu Zhu, Po-Shen Hsin

A fundamental problem in fault-tolerant quantum computation is the tradeoff between universality and dimensionality, exemplified by the the Bravyi-König bound for $n$-dimensional topological stabilizer codes. In this work, we extend topological Pauli stabilizer codes to a broad class of $n$-dimensional Clifford hierarchy stabilizer codes. These codes correspond to the $(n+1)$D Dijkgraaf-Witten gauge theories with non-Abelian topological order. We construct transversal non-Clifford gates through automorphism symmetries represented by cup products. In 2D, we obtain the first transversal non-Clifford logical gates including T and CS for Clifford stabilizer codes, using the automorphism of the twisted $\mathbb{Z}_2^3$ gauge theory (equivalent to $\mathbb{D}_4$ topological order). We also combine it with the just-in-time decoder to fault-tolerantly prepare the logical T magic state in $O(d)$ rounds via code switching. In 3D, we construct a transversal logical $\sqrt{\text{T}}$ gate in a non-Clifford stabilizer code at the third level of the Clifford hierarchy, located on a tetrahedron corresponding to a twisted $\mathbb{Z}_2^4$ gauge theory. Our constructions surpass the Bravyi-König bound by achieving the logical gates in the $(n+1)$-th level of Clifford hierarchy in $n$ spatial dimension.

quant-pharXiv:2511.02900•Physical Review Letters•Nov 6, 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

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

Generalised Clifford groups and simulation of associated quantum circuits

Sean Clark, Richard Jozsa, Noah Linden

Quantum computations that involve only Clifford operations are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup G of U(d). In particular we seek G such that G tensor G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2 we exhaustively treat all finite subgroups of U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups G_n generated by X and the n^th root of Z.

arXiv:quant-ph/0701103•Jan 15, 2007•4 citations
The Clifford hierarchy C1⊂C2⊂C3⊂⋯\mathsf{C}_1 \subset \mathsf{C}_2 \subset \mathsf{C}_3 \subset \cdotsC1​⊂C2​⊂C3​⊂⋯ is usually defined inductively: a gate UUU is at level k+1k+1k+1 if it maps every Pauli to level kkk under conjugation. This paper shows that this definition is the shadow of a cohomological statement: the boundary between C2\mathsf{C}_2C2​ (Clifford) and C3\mathsf{C}_3C3​ (magic) is witnessed by a non-trivial element of H2(Sp(4,F2);Z2)H^2(\mathrm{Sp}(4,\mathbb{F}_2);\mathbb{Z}_2)H2(Sp(4,F2​);Z2​), the obstruction to lifting a projective representation of the symplectic group to a genuine one. The T gate is the canonical representative of this non-trivial class. The obstruction is proved computationally for Sp(4,F2)\mathrm{Sp}(4,\mathbb{F}_2)Sp(4,F2​) via the Weil representation: for any BFS-lifted section g↦Wgg \mapsto W_gg↦Wg​, there exist elements ggg of Sp-order ddd for which Wgd=−IW_g^d = -IWgd​=−I (not +I+I+I), directly witnessing the Z2\mathbb{Z}_2Z2​ obstruction. Sixty-seven such witnesses are found; the simplest has Sp-order 2 with Clifford lift of order 4. The TWIST opcode in the Origami ISA counts the number of times this cohomology class is "charged" in a circuit. TWIST =0= 0=0 is equivalent to the circuit lying in the trivial Z2\mathbb{Z}_2Z2​ class, and hence to Gottesman-Knill classical simulability. This makes the Schur multiplier Z2\mathbb{Z}_2Z2​ a computable certificate for quantum advantage. The paper unifies three apparently distinct Z2\mathbb{Z}2Z2 obstructions: (1) the Schur multiplier of Sp(4,F2)\mathrm{Sp}(4,\mathbb{F}2)Sp(4,F2), witnessed by the T gate; (2) Pauli anti-commutation, XZ=−ZXXZ = -ZXXZ=−ZX; (3) the SPT invariant of the cluster state, whose virtual bond symmetry satisfies (UgxUgz)(UgzUgx)−1=−I∈H2(Z2×Z2;U(1))=Z2(U{g_x} U{g_z})(U_{g_z} U_{g_x})^{-1} = -I \in H^2(\mathbb{Z}_2 \times \mathbb{Z}_2; U(1)) = \mathbb{Z}_2(Ugx​Ugz​)(Ugz​​Ugx​​)−1=−I∈H2(Z2​×Z2​;U(1))=Z2​. These are shown to be three languages for one object, related by explicit inflation and restriction maps. Keywords Clifford hierarchy, group cohomology, Schur multiplier, symplectic group, metaplectic representation, Weil representation, T gate, magic states, quantum advantage, Gottesman-Knill theorem, symmetry-protected topological phases, cluster state, Origami ISA, TWIST opcode, H2H^2H2 obstruction
The Clifford hierarchy C1⊂C2⊂C3⊂⋯\mathsf{C}_1 \subset \mathsf{C}_2 \subset \mathsf{C}_3 \subset \cdotsC1​⊂C2​⊂C3​⊂⋯ is usually defined inductively: a gate UUU is at level k+1k+1k+1 if it maps every Pauli to level kkk under conjugation. This paper shows that this definition is the shadow of a cohomological statement: the boundary between C2\mathsf{C}_2C2​ (Clifford) and C3\mathsf{C}_3C3​ (magic) is witnessed by a non-trivial element of H2(Sp(4,F2);Z2)H^2(\mathrm{Sp}(4,\mathbb{F}_2);\mathbb{Z}_2)H2(Sp(4,F2​);Z2​), the obstruction to lifting a projective representation of the symplectic group to a genuine one. The T gate is the canonical representative of this non-trivial class. The obstruction is proved computationally for Sp(4,F2)\mathrm{Sp}(4,\mathbb{F}_2)Sp(4,F2​) via the Weil representation: for any BFS-lifted section g↦Wgg \mapsto W_gg↦Wg​, there exist elements ggg of Sp-order ddd for which Wgd=−IW_g^d = -IWgd​=−I (not +I+I+I), directly witnessing the Z2\mathbb{Z}_2Z2​ obstruction. Sixty-seven such witnesses are found; the simplest has Sp-order 2 with Clifford lift of order 4. The TWIST opcode in the Origami ISA counts the number of times this cohomology class is "charged" in a circuit. TWIST =0= 0=0 is equivalent to the circuit lying in the trivial Z2\mathbb{Z}_2Z2​ class, and hence to Gottesman-Knill classical simulability. This makes the Schur multiplier Z2\mathbb{Z}_2Z2​ a computable certificate for quantum advantage. The paper unifies three apparently distinct Z2\mathbb{Z}2Z2 obstructions: (1) the Schur multiplier of Sp(4,F2)\mathrm{Sp}(4,\mathbb{F}2)Sp(4,F2), witnessed by the T gate; (2) Pauli anti-commutation, XZ=−ZXXZ = -ZXXZ=−ZX; (3) the SPT invariant of the cluster state, whose virtual bond symmetry satisfies (UgxUgz)(UgzUgx)−1=−I∈H2(Z2×Z2;U(1))=Z2(U{g_x} U{g_z})(U_{g_z} U_{g_x})^{-1} = -I \in H^2(\mathbb{Z}_2 \times \mathbb{Z}_2; U(1)) = \mathbb{Z}_2(Ugx​Ugz​)(Ugz​​Ugx​​)−1=−I∈H2(Z2​×Z2​;U(1))=Z2​. These are shown to be three languages for one object, related by explicit inflation and restriction maps. Keywords Clifford hierarchy, group cohomology, Schur multiplier, symplectic group, metaplectic representation, Weil representation, T gate, magic states, quantum advantage, Gottesman-Knill theorem, symmetry-protected topological phases, cluster state, Origami ISA, TWIST opcode, H2H^2H2 obstruction
Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup GGG of U(d)U(d)U(d). In particular we seek GGG such that G⊗GG\otimes GG⊗G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2d = 2d=2 we exhaustively treat all finite irreducible subgroups of U(2)U(2)U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the nthn^{\rm th}nth root of ZZZ for n∈Nn \in \Nn∈N.
A fundamental problem in fault-tolerant quantum computation is the tradeoff between universality and dimensionality, exemplified by the the Bravyi-König bound for nnn-dimensional topological stabilizer codes. In this work, we extend topological Pauli stabilizer codes to a broad class of nnn-dimensional Clifford hierarchy stabilizer codes. These codes correspond to the (n+1)(n+1)(n+1)D Dijkgraaf-Witten gauge theories with non-Abelian topological order. We construct transversal non-Clifford gates through automorphism symmetries represented by cup products. In 2D, we obtain the first transversal non-Clifford logical gates including T and CS for Clifford stabilizer codes, using the automorphism of the twisted Z23\mathbb{Z}_2^3Z23​ gauge theory (equivalent to D4\mathbb{D}_4D4​ topological order). We also combine it with the just-in-time decoder to fault-tolerantly prepare the logical T magic state in O(d)O(d)O(d) rounds via code switching. In 3D, we construct a transversal logical T\sqrt{\text{T}}T​ gate in a non-Clifford stabilizer code at the third level of the Clifford hierarchy, located on a tetrahedron corresponding to a twisted Z24\mathbb{Z}_2^4Z24​ gauge theory. Our constructions surpass the Bravyi-König bound by achieving the logical gates in the (n+1)(n+1)(n+1)-th level of Clifford hierarchy in nnn spatial dimension.
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 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.
Quantum computations that involve only Clifford operations are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup G of U(d). In particular we seek G such that G tensor G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2 we exhaustively treat all finite subgroups of U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups G_n generated by X and the n^th root of Z.