When is the Clifford hierarchy generalized semi-Clifford?

Two structures that describe gates in the hierarchy

The Clifford hierarchy starts from the Pauli group C_1(n) = P(n) and is defined recursively by C_{k+1}(n) = {U : U P(n) U† ⊆ C_k(n)}. It was introduced by Gottesman and Chuang for fault-tolerant quantum computation, where gates in the hierarchy can be implemented using teleportation. Unlike the Pauli group C_1(n) and the Clifford group C_2(n), C_k(n) is not a group for k≥3, so its structure has remained obscure.

Zeng, Chen, and Chuang introduced two structural descriptions. A gate U is semi-Clifford (SC) if conjugation by U maps a maximal abelian subgroup of P(n) to a maximal abelian subgroup of P(n). It is generalized semi-Clifford (GSC) if it maps the linear span of some maximal abelian subgroup to the linear span of another. Equivalently, U is semi-Clifford when U = C_1 D C_2 and generalized semi-Clifford when U = C_1 Π D C_2, where C_1, C_2 are Clifford, D is diagonal, and Π is a permutation in the computational basis. The paper writes SC(n) and GSC(n) for the two sets.

The distinction matters because the two conditions are not the same test. Semi-Clifford requires a maximal abelian subgroup to map exactly onto another one; generalized semi-Clifford only requires the span of one to map onto the span of another, which is a strictly weaker requirement. A gate can therefore be generalized semi-Clifford without being semi-Clifford, and the paper's two classification results have different boundaries.

Semi-Clifford holds only in small cases

Theorem 1 states that C_k(n) ⊆ SC(n) if and only if k≤2, or n≤2, or k=3 and n≤6. This is a complete characterization, not a partial one: outside those three regions, some gate in C_k(n) is not semi-Clifford.

Most of the picture was already in the literature. Zeng, Chen, and Chuang proved that every gate is semi-Clifford at every level on at most two qubits and at the third level on three qubits, and constructed a gate in C_4(3) \ SC(3). Beigi and Shor reported a seven-qubit third-level counterexample by Gottesman and Mochon. Anderson and Connelly established C_3(4) ⊆ SC(4). The remaining open cases were C_3(5) and C_3(6), which this paper settles in Theorem 5: for n=5 and n=6, C_3(n) ⊆ SC(n).

The proof of Theorem 5 reduces a third-level gate to the form U|x,y⟩ = e^{iθ(x,y)}|x, y+q(x)⟩, where q is a quadratic function over F_2, using two structural results from earlier work. The key observation is that membership in C_3(n) imposes strong restrictions on the phase θ(x,y). After a further change of basis by a target Clifford, the gate reduces to M = Σ_x ζ(x)|x⟩⟨x| ⊗ P_{v(x)}, where P_{v(x)} is a Pauli operator on the y-qubits. The remaining check is that the P_{v(x)} mutually commute, which holds for n≤6 by a dimension argument. Since U = C_1 M C_2 with Clifford C_1, C_2, this places U in SC(n).

Generalized semi-Clifford survives to level four

Theorem 6 proves C_4(n) ⊆ GSC(n) for any n, using a group-theoretic argument rather than a case enumeration. For U in C_4(n), the proof studies the group Γ(U) = ⟨P(n), U P(n) U†⟩ inside the projective unitary group. The central observation is that if Γ(U) is a finite 2-group, then U is generalized semi-Clifford. It therefore suffices to show Γ(U) is a finite 2-group for U in C_4(n).

The argument runs through the corrections h_v = U P_v U†. Because the corrections lie in C_3(n), the conjugates h_v P(n) h_v† consist of Clifford gates and generate a finite group G normalized by the 2-group U P(n) U†. One can show that U P(n) U† fixes a Sylow 2-subgroup of G, which contains P(n) and hence every h_v P(n) h_v†, so that subgroup equals G and Γ(U) is a 2-group.

Combined with earlier results, this gives the positive half of the generalized semi-Clifford classification: C_k(n) ⊆ GSC(n) whenever k≤4 or n≤3. The paper notes that the inclusion C_4(n) ⊆ GSC(n) was obtained independently by similar methods in related work.

Counterexamples appear at five qubits and level five

The positive results stop at a sharp boundary. Theorem 1 states that if k≥5 and n≥5, then C_k(n) is not contained in GSC(n). Theorem 15 makes this constructive: for every k≥5 and n≥5 there is a gate U in F_2(2, n−2) such that U ∈ C_k(n) \ C_{k−1}(n) and U is not generalized semi-Clifford. The gate has exact level k, so the failure is not an artifact of a gate that happens to sit at a lower level.

The construction goes through the class F_2(n_c, n_t), the gates that permute the computational basis states of n_c control qubits and apply a Clifford block V_x to the remaining n_t = n − n_c qubits. Proposition 14 shows that F_2(n_c, n_t) ⊆ GSC(n_c + n_t) if and only if n_c ≤ 1 or n_t ≤ 2. Consequently the first possible non-generalized semi-Clifford gate in this class needs n_c ≥ 2 and n_t ≥ 3, which requires n = n_c + n_t ≥ 5. The paper's counterexamples sit exactly at that threshold.

The paper also records that a different counterexample in C_k(n) \ GSC(n) was obtained independently elsewhere and arises from a different construction. The authors state they learned of those results after independently obtaining their own.

The four-qubit case is reduced but not closed

The one region the paper does not fully settle is n=4 with k≥5. For that region it proves a partial result: if U ∈ C_k(4) and, up to a scalar, U can be defined over Q(i), then U ∈ GSC(4). Such gates are called Gaussian, meaning the conductor cond(U) equals 2, where the conductor is the least r≥2 such that some nonzero scalar multiple of U has all entries in K_r = Q(ζ_{2^r}).

The general case is reduced to a single level. Proposition F.7 shows that C_k(4) ⊆ GSC(4) for every k if and only if C_4290(4) ⊆ GSC(4): a counterexample, if one exists, can be taken of conductor at most 285 and level at most 4290. The paper is explicit that this reduction does not make the problem tractable. The diagonal gates of conductor at most 285 alone give 2^{285·15} ≈ 10^{1287} gates of C_4290(4) up to scalars, and even after removing Clifford factors on both sides there remain more than 10^{1260} gates to test.

The authors therefore propose Conjecture 2, that C_k(n) ⊆ GSC(n) if and only if k≤4 or n≤4, together with a strategy to prove it. The strategy is a conductor descent argument: given a gate whose corrections are generalized semi-Clifford but not all Gaussian, construct another gate U′ with the same generalized semi-Clifford status and strictly smaller conductor. For n=3 this argument is carried out in Theorem 11 and Theorem 12, proving C_k(3) ⊆ GSC(3) for every k by induction on the pair (r, k) in lexicographic order. For n=4 the analogous step is stated as Conjecture 1, because the finite case analysis needed to find a Pauli Q with U Q U† a Pauli does not yet go through.

A finer structure than generalized semi-Clifford

The paper goes beyond the generalized semi-Clifford description by introducing n_c-generalized semi-Clifford gates. For 0 ≤ n_c ≤ n, a gate U is n_c-generalized semi-Clifford if U A_S U† = A_T for some isotropic subspaces S, T of F_2^{2n} of dimension n_c. Under this definition the generalized semi-Clifford gates are exactly the n-generalized semi-Clifford gates, and every gate is 0-generalized semi-Clifford trivially. A gate can be n_c-generalized semi-Clifford for several values of n_c.

Lemma 13 gives the equivalent circuit form: a gate U in C(n) lies in F(n_c, n_t), with n_t = n − n_c, if and only if it is n_c-generalized semi-Clifford. Concretely, such a gate can be written as C_1 (Σ_x |π(x)⟩⟨x| ⊗ V_x) C_2, where C_1 and C_2 are Clifford, π permutes the computational basis states of the n_c control qubits, and each V_x acts on the remaining n_t qubits.

Conjecture 3 refines the original conjecture of Zeng, Chen, and Chuang. It states that every gate in C(n) is n_c-generalized semi-Clifford for some 1 ≤ n_c ≤ n, and more precisely that if U ∈ C_k(n) with k≥3, then U = C_1 (Σ_x |π(x)⟩⟨x| ⊗ V_x) C_2 with each V_x ∈ C_{k−3}(n_t). The level drops by three across the decomposition. The conjecture is consistent with what is already proved: for k=3 and k=4 it says exactly that C_3(n) and C_4(n) are generalized semi-Clifford, which holds. For k=5 it predicts Clifford blocks V_x ∈ C_2(n_t), and if true, Proposition 14 would then give C_5(4) ⊆ GSC(4), since n_c ≤ 1 or n_t ≤ 2 whenever n_c ≥ 1 and n_c + n_t = 4.

What the boundary means for readers

The most decision-relevant output of this paper is a two-parameter map. If you are working with a gate in C_k(n) and want to know whether the generalized semi-Clifford description applies, the answer is yes whenever k≤4 or n≤3, and no for every k≥5 and n≥5, where the failure is witnessed by an explicit gate of exact level k. The semi-Clifford description is narrower: it applies only when k≤2, n≤2, or k=3 with n≤6.

The region that deserves the most caution is n=4 with k≥5. There the paper proves a partial result for Gaussian gates, reduces the general question to a single level, and states the remaining step as a conjecture rather than a theorem. Readers should treat C_k(4) ⊆ GSC(4) for all k as unproven, and should not read the Gaussian result as covering all four-qubit gates at level five and above.

The paper's own framing of what comes next is specific. The first direction it names is completing the conductor descent argument for n=4; success there would finish the picture of when C_k(n) ⊆ GSC(n). It also suggests exploring whether a finer structure is determined by the triple (r, k, n), where r is the conductor, and notes that some techniques should extend to qudits, where a prime local dimension d≥3 offers more algebraic tools that could substantially reduce the finite-case analysis. The practical threshold to carry away is therefore the pair (k, n): below it the generalized semi-Clifford description is a theorem, at k≥5 and n≥5 it is provably false, and n=4 with k≥5 is the one place where the answer still depends on an open conjecture.

Sources used in this answer