Third-level Clifford-hierarchy gates on at most six qubits are semi-Clifford

Yuxuan Zhang

Full manuscript (PDF, 10 pages) · Manuscript source, exact checker, reviews and provenance (ZIP)

A complete proof candidate. Three separate internal AI reviews and a final internal audit of the manuscript and program found no mathematical gap. External specialist confirmation and literature priority remain unverified; arXiv was searched through 26 September 2026. Two steps are computer-assisted, and both reproduce exactly with a program that needs only the Python standard library.

The question

The Clifford hierarchy of Gottesman and Chuang [1] starts from the Pauli group \(\mathcal C_1(n)\) and defines \(\mathcal C_{k+1}(n)\) as the unitaries that conjugate every Pauli operator into \(\mathcal C_k(n)\), so that \(\mathcal C_2(n)\) is the Clifford group. A gate is semi-Clifford if it is a diagonal gate up to Clifford gates on each side, \(C_LDC_R\). Such gates can be applied with a simpler teleportation circuit, which is why it matters which third-level gates have this form.

Zeng, Chen and Chuang [2] proved that every third-level gate on at most three qubits is semi-Clifford and conjectured it in general. Beigi and Shor [3] proved the weaker statement that every third-level gate is generalized semi-Clifford, and reported a seven-qubit third-level gate of Gottesman and Mochon that is not semi-Clifford. Anderson and Connelly [4] settled four qubits. He, Robitaille and Tan [5] characterized the third-level permutation gates and showed that those on at most six qubits are semi-Clifford, and they state that the question for general gates on five or six qubits is open. The question [6] is the least number of qubits \(n_{\min}\) on which the third level contains a gate that is not semi-Clifford; it was known to lie in \(\{5,6,7\}\).

It is seven. Every third-level gate on five or six qubits is semi-Clifford.

The structure

The proof gives more than the yes-or-no answer. On \(n\le 6\) qubits every third-level gate has the form \(C_1D_1\,\pi\,D_hD_2C_2\): Clifford gates \(C_1,C_2\) on the outside, diagonal Clifford gates \(D_1,D_2\), a single layer \(\pi\) of Toffoli gates whose control and target qubits are disjoint, and a product \(D_h\) of \(T\), controlled-\(S\) and doubly controlled-\(Z\) gates acting only on the non-target qubits. Conjugating the targets by Hadamard gates turns \(\pi D_h\) into a diagonal gate, which exhibits the semi-Clifford form explicitly.

The argument

The only non-textbook inputs are the theorem of Beigi and Shor and a factorization of Zeng, Chen and Chuang, which together write a third-level gate as \(C_L\Pi DC_R\) with \(\Pi\) a permutation. One observation removes the need for anything more. Conjugating a Pauli operator by \(\Pi D\) gives a monomial Clifford gate, and the permutation part of a monomial Clifford gate must be affine. So every conjugate \(\Pi\tau_b\Pi^{-1}\) of a translation is affine, even without knowing that \(\Pi\) itself lies in the third level.

Permutations with this property correspond to commutative, associative algebra structures on \(\mathbb F_2^n\) in which every square vanishes — the correspondence of Caranti, Dalla Volta and Sala [7] between abelian regular subgroups of the affine group and radical rings. In such an algebra a nonzero triple product \(xyz\) forces the seven elements \(x,y,z,xy,xz,yz,xyz\) to be linearly independent. So below seven dimensions every triple product vanishes, and that is exactly the condition for the permutation to be a single Toffoli layer up to affine maps. The free algebra of this kind on three generators produces the seven-qubit counterexample, which is why seven is the threshold.

Up to affine changes of coordinates, the layers on at most six qubits fall into ten classes, organized by the span of their quadratic forms. One step of this classification — that each of the three nondegenerate types of line on the Klein quadric is a single orbit of \(\mathrm{GL}(4,2)\) — is verified by computation. For each class the group of admissible diagonal phases is determined exactly. It is generated by the obvious phases, namely Clifford diagonals on either side of the layer and third-level diagonals on the non-target qubits (the qubit case of the classification of Cui, Gottesman and Krishna [8]), and an exact computation certifies that there are no others. That structure gives the factorization above.

Verification

The argument and the program were produced by an AI research agent. The program uses only the Python standard library and exact integer arithmetic, and prints 54 lines of checks in about seven seconds:

python3 check_c3_n5_n6.py | diff - expected_stdout.txt

It derives each of the ten admissible-phase groups twice, by routes that share no code beyond \(\mathbb Z_8\) linear algebra — once from the paper’s criterion and once directly from the definition of the hierarchy — and certifies each group’s order with a kernel certificate. The orders, \(2^{38},2^{38},2^{33}\) on five qubits and \(2^{56},2^{56},2^{47},2^{47},2^{47},2^{47},2^{43}\) on six, equal the orders of the subgroups generated by the obvious phases. Twenty single-point mutations of the program each make it fail, and isolated runs with networking disabled reproduce its output byte for byte.

Three AI reviewers checked the argument in isolated contexts, each recomputing with its own code the phase groups it covered; the last worked directly from the definition of the hierarchy and shared none of the program’s routes. A final audit recomputed every number in the manuscript and checked the three load-bearing quotations word for word against the sources.

Reproduction establishes only that the program computes what it prints. The reductions it relies on are established by the written argument.

What this establishes, and what it does not

The value \(n_{\min}=7\) is settled, together with the explicit form of every third-level gate on at most six qubits. The lower bound is computer-assisted in two places: the inclusion of the admissible phases in the obvious ones, for each of the ten classes, and the orbit statement in the classification. The seven-qubit upper bound is proved by hand for an explicit permutation gate and confirmed by the program; it reproves the Gottesman–Mochon bound without relying on it.

Nothing is claimed about the structure of the third level on seven or more qubits, where the permutation part can have several Toffoli layers. For permutation gates alone, semi-Cliffordness on at most six qubits is due to He, Robitaille and Tan [5]; what is new here is control of the diagonal factor, which is what general gates add.

References

1. D. Gottesman and I. L. Chuang, Quantum teleportation is a universal computational primitive, Nature 402, 390–393 (1999), arXiv:quant-ph/9908010.
2. 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, Phys. Rev. A 77, 042313 (2008), arXiv:0712.2084.
3. S. Beigi and P. W. Shor, \(\mathcal C_3\), semi-Clifford and generalized semi-Clifford operations, Quantum Inf. Comput. 10, 41–59 (2010), arXiv:0810.5108.
4. J. T. Anderson and A. Connelly, Affine equivalence in the Clifford hierarchy, arXiv:2507.14370.
5. Z. He, L. Robitaille and X. Tan, Characterization of permutation gates in the third level of the Clifford hierarchy, arXiv:2510.04993.
6. Quantum Information and Quantum Computation Open Problem Zoo, Smallest qubit number for a non-semi-Clifford third-level gate.
7. A. Caranti, F. Dalla Volta and M. Sala, Abelian regular subgroups of the affine group and radical rings, Publ. Math. Debrecen 69, 297–308 (2006), arXiv:math/0510166.
8. S. X. Cui, D. Gottesman and A. Krishna, Diagonal gates in the Clifford hierarchy, Phys. Rev. A 95, 012329 (2017), arXiv:1608.06596.
9. T. Kassis, V. Agarwal, Y. He, D. Patel and A. M. Brueckner, Scientific Agent Skills: A Library of Procedural Knowledge for Research Agents, arXiv:2609.00065v2. Writing guidance consulted at commit 330c8e764435.