Smallest qubit number for a non-semi-Clifford third-level gate

Problem

What is the smallest number of qubits on which the third level of the Clifford hierarchy contains a gate that is not semi-Clifford? For \(n\geq1\) qubits, let \(\mathcal{P}_n\) be the Pauli group with arbitrary global phases, consisting of the operators \(e^{i\theta}P_1\otimes\cdots\otimes P_n\) with \(\theta\in\mathbb{R}\) and \(P_j\in\{I,X,Y,Z\}\), and define the Clifford hierarchy recursively by

\begin{equation} \mathcal{C}_1(n):=\mathcal{P}_n, \qquad \mathcal{C}_{k+1}(n):= \bigl\{U\in U(2^n):UPU^\dagger\in\mathcal{C}_k(n) \ \text{for every}\ P\in\mathcal{P}_n\bigr\}, \qquad k\geq1. \tag{1} \end{equation}

Thus \(\mathcal{C}_2(n)\) is the Clifford group. A unitary is semi-Clifford when it can be written as \(C_LDC_R\) with \(C_L,C_R\in\mathcal{C}_2(n)\) and \(D\) diagonal in the computational basis; let \(\mathrm{SC}(n)\) denote the set of such unitaries. The quantity sought is

\begin{equation} n_{\min}:=\min\bigl\{n\geq1: \mathcal{C}_3(n)\setminus\mathrm{SC}(n)\neq\varnothing\bigr\}, \tag{2} \end{equation}

where \(\mathcal{C}_3(n)\) is the third level in Eq. (1). The known results give \(n_{\min}\in\{5,6,7\}\). A complete answer determines the value of \(n_{\min}\) in Eq. (2); equivalently, it decides for \(n=5\) and for \(n=6\) whether every gate in \(\mathcal{C}_3(n)\) is semi-Clifford.

Source

Zeng, Chen, and Chuang conjectured that every third-level gate is semi-Clifford and proved it for at most three qubits [ZCC08]; Beigi and Shor reported the seven-qubit counterexample of Gottesman and Mochon [BS10]. Anderson and Connelly identified four qubits as the smallest case in which the structure of the third level was not fully known, and settled it [AC25]. He, Robitaille, and Tan state explicitly, in Section 2.1 (page 2:6) of the TQC 2026 version, that it is an open problem whether a third-level gate on five or six qubits can fail to be semi-Clifford [HRT26]. Eq. (2) restates that explicit question as the determination of the least such number of qubits.

Progress

Zeng, Chen, and Chuang proved that every gate of every level is semi-Clifford on one or two qubits (Theorem 1) and that every third-level gate on three qubits is semi-Clifford (Theorem 2, by exhaustive computation), while for every level \(k\geq4\) some three-qubit gates are not semi-Clifford (Theorem 3):

\begin{equation} \mathcal{C}_3(n)\subseteq\mathrm{SC}(n)\quad(1\leq n\leq3), \qquad \mathcal{C}_k(3)\not\subseteq\mathrm{SC}(3)\quad(k\geq4). \tag{3} \end{equation}

The left part of Eq. (3) gives \(n_{\min}\geq4\). Together with the two-qubit theorem, the right part shows that the analogue of \(n_{\min}\) at every level \(k\geq4\) equals three, so the third level is the only level at which this threshold is undetermined [ZCC08].
Beigi and Shor reported, in Section 1.1, a seven-qubit construction of Gottesman and Mochon: a product of three controlled-swap gates and four doubly controlled \(Z\) gates that lies in \(\mathcal{C}_3(7)\) but is not semi-Clifford. Hence

\begin{equation} \mathcal{C}_3(7)\setminus\mathrm{SC}(7)\neq\varnothing, \qquad n_{\min}\leq7. \tag{4} \end{equation}

Their Theorem 1.1 shows that every third-level gate is generalized semi-Clifford [BS10]; by Proposition 2 of [ZCC08], such a gate factors as \(C_L\Pi DC_R\) with Clifford gates \(C_L,C_R\), a computational-basis permutation \(\Pi\), and a diagonal \(D\). For a gate in \(\mathcal{C}_3(n)\setminus\mathrm{SC}(n)\), the permutation \(\Pi\) in such a factorization cannot be a Clifford gate.
Anderson and Connelly proved, in Section 4 of a 2025 preprint, that every four-qubit third-level gate is semi-Clifford, so that, with Eqs. (3) and (4),

\begin{equation} \mathcal{C}_3(4)\subseteq\mathrm{SC}(4), \qquad n_{\min}\in\{5,6,7\}. \tag{5} \end{equation}

The proof starts from the generalized semi-Clifford form, uses the classification of four-bit permutations into affine equivalence classes (only one class, containing the Toffoli gate, lies in the third level but not the Clifford group), reduces the diagonal factor to finitely many equivalence classes, and checks every remaining class by computer (Algorithm 1). The authors remark that the approach might settle five qubits with ample computational resources, whereas six qubits likely requires further theoretical reductions [AC25].
He, Robitaille, and Tan characterized the permutation gates in the third level. In Appendix A of the full version they prove that every third-level permutation gate on at most six qubits is semi-Clifford, and that seven is the least number of qubits carrying a non-semi-Clifford third-level permutation gate (Theorem A.6):

\begin{equation} \mathcal{C}_3(n)\cap\mathrm{Perm}(2^n)\subseteq\mathrm{SC}(n) \qquad(n\leq6), \tag{6} \end{equation}

where \(\mathrm{Perm}(2^n)\) denotes the computational-basis permutation matrices. Their seven-qubit permutation \(U_3\) is Clifford-conjugate to the Gottesman–Mochon gate (Proposition 5.8), and their Lemma A.3 shows that \(U\otimes I\) is not semi-Clifford whenever \(U\) is not, so \(\mathcal{C}_3(n)\setminus\mathrm{SC}(n)\neq\varnothing\) for every \(n\geq n_{\min}\). Eq. (6) does not cover general gates: by their Corollary 3.9, every third-level gate has the form \(C_L\pi DC_R\) with Clifford gates \(C_L,C_R\), a permutation gate \(\pi\in\mathcal{C}_3(n)\), and a diagonal \(D\), so a counterexample on five or six qubits would have to arise from such a product in which \(\pi\) alone is semi-Clifford. The TQC 2026 version states in Section 2.1 that the five- and six-qubit cases remain open [HRT26].
De Silva and Lautsch constructed, in a preliminary preprint of 10 September 2026, a five-qubit gate \(V\), a product of two singly controlled Clifford gates, with (Theorem 8.1)

\begin{equation} V\in\mathcal{C}_5(5)\setminus\mathcal{C}_4(5), \qquad V\ \text{is not generalized semi-Clifford}. \tag{7} \end{equation}

Tensoring with identities gives such gates in \(\mathcal{C}_k(n)\) for all \(n\geq5\) and \(k\geq5\), and \(V^\dagger\) lies in no level of the hierarchy (Theorem 8.2) [dSL26]. Since every third-level gate is generalized semi-Clifford [BS10] and \(V\notin\mathcal{C}_4(5)\supseteq\mathcal{C}_3(5)\), Eq. (7) has no bearing on \(n_{\min}\).

Comment

The unresolved cases are \(n=5\) and \(n=6\): it is unknown whether \(\mathcal{C}_3(5)\) or \(\mathcal{C}_3(6)\) contains a gate that is not semi-Clifford. A proof that all gates in both are semi-Clifford would give \(n_{\min}=7\), while one counterexample on five or six qubits would fix \(n_{\min}\) at the smallest such size. The permutation-gate result in Eq. (6) does not exclude products of third-level permutations with non-Clifford diagonal gates, and the fifth-level gate in Eq. (7) does not supply a third-level counterexample. This is a finite-size question; the unrestricted conjecture that all third-level gates are semi-Clifford is already refuted by Eq. (4). The four-qubit input in Eq. (5) is a computer-assisted result in a preprint. Literature checked through 15 September 2026; no resolution of the five- or six-qubit case was found. The zoo’s record “Semi-Clifford structure of two-qudit hierarchy gates above the third level” asks the analogous semi-Clifford question for two qudits of odd prime dimension at levels four and above.

References

[ZCC08]: B. Zeng, X. Chen, and I. L. Chuang, “Semi-Clifford operations, structure of \(\mathcal{C}_k\) hierarchy, and gate complexity for fault-tolerant quantum computation,” Physical Review A 77, 042313 (2008).DOI arXiv
[BS10]: S. Beigi and P. W. Shor, “\(\mathcal{C}_3\), semi-Clifford and generalized semi-Clifford operations,” Quantum Information and Computation 10, 41–59 (2010).DOI arXiv
[AC25]: J. T. Anderson and A. Connelly, “Affine equivalence in the Clifford hierarchy,” arXiv preprint (2025).DOI arXiv
[HRT26]: Z. He, L. Robitaille, and X. Tan, “Characterization of permutation gates in the third level of the Clifford hierarchy,” in 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026), LIPIcs 389, 2:1–2:17 (2026); full version arXiv:2510.04993.DOI arXiv
[dSL26]: N. de Silva and O. Lautsch, “The generalised semi-Clifford conjecture is false,” arXiv preprint, preliminary draft (2026).DOI arXiv

Smallest qubit number for a non-semi-Clifford third-level gate

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems