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.
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.
The Clifford hierarchy C1⊂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 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 ∪kCk 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∈C3 on the span of maximal stabilizer subgroups (arXiv:2006.14040). By extending their fixed-point arguments to the group Γ1(U) generated by UPU† and beyond, we prove the conjecture for k≤4 and any prime dimension d.
Our proof centers on conjugation groups Γ1(U),Γ2(U),… of U∈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.
Teleportation is a crucial element in fault-tolerant quantum computation and a complete understanding of its capacity is very important for the practical implementation of optimal fault-tolerant architectures. It is known that stabilizer codes support a natural set of gates that can be more easily implemented by teleportation than any other gates. These gates belong to the so-called Ck hierarchy introduced by Gottesman and Chuang [Nature (London) 402, 390 (1999)]. Moreover, a subset of Ck gates, called semi-Clifford operations, can be implemented by an even simpler architecture than the traditional teleportation setup [X. Zhou, D. W. Leung, and I. L. Chuang, Phys. Rev. A 62, 052316 (2000)]. However, the precise set of gates in Ck remains unknown, even for a fixed number of qubits n, which prevents us from knowing exactly what teleportation is capable of. In this paper we study the structure of Ck in terms of semi-Clifford operations, which send by conjugation at least one maximal Abelian subgroup of the n-qubit Pauli group into another one. We show that for n=1,2, all the Ck gates are semi-Clifford, which is also true for n=3,k=3. However, this is no longer true for n>2,k>3. To measure the capability of this teleportation primitive, we introduce a quantity called ``teleportation depth,'' which characterizes how many teleportation steps are necessary, on average, to implement a given gate. We calculate upper bounds for teleportation depth by decomposing gates into both semi-Clifford Ck gates and those Ck gates beyond semi-Clifford operations, and compare their efficiency.
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.
Fault-tolerant quantum computation is a basic problem in quantum computation, and teleportation is one of the main techniques in this theory. Using teleportation on stabilizer codes, the most well-known quantum codes, Pauli gates and Clifford operators can be applied fault-tolerantly. Indeed, this technique can be generalized for an extended set of gates, the so called Ck hierarchy gates, introduced by Gottesman and Chuang (Nature, 402, 390-392). Ck gates are a generalization of Clifford operators, but our knowledge of these sets is not as rich as our knowledge of Clifford gates. Zeng et al. in (Phys. Rev. A 77, 042313) raise the question of the relation between Ck hierarchy and the set of semi-Clifford and generalized semi-Clifford operators. They conjecture that any Ck gate is a generalized semi-Clifford operator. In this paper, we prove this conjecture for k=3. Using the techniques that we develop, we obtain more insight on how to characterize C3 gates. Indeed, the more we understand C3, the more intuition we have on Ck, k≥4, and then we have a way of attacking the conjecture for larger k.
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.
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ΠDC2 for Clifford gates C1,C2, 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.