A cryptography shortcut helps classify quantum gates

A hierarchy with unusual rules

The Clifford hierarchy organizes quantum gates by how they transform Pauli operations, which constitute its first level. Clifford gates occupy the second level: conjugating a Pauli operation by a Clifford gate produces another Pauli operation. Higher levels repeat this rule, requiring transformed Paulis to belong to the preceding level.

Understanding this structure helps restrict which transversal gates can be available to quantum error-correcting codes. But the hierarchy is not a toolbox whose contents can always be combined freely. From the third level onward, its gates do not form a group: composing two gates at a given level need not keep the result there.

The paper focuses heavily on permutation gates. These rearrange computational-basis states—the binary strings labeling a quantum system’s standard basis. Four qubits have 16 such states, giving 16 factorial possible rearrangements. Testing them individually would be a formidable task.

Borrowing a classification from cryptography

Cryptographers already study reversible transformations of bit strings. One organizing principle is affine equivalence: two permutations count as equivalent if one can be obtained from the other by placing invertible affine transformations before and after it.

For these quantum gates, affine transformations are precisely the permutations generated by controlled-NOT gates and bit flips. They are Clifford operations. Surrounding a gate with Clifford operations preserves its membership at every hierarchy level from the second upward. This does not necessarily preserve membership in the first, Pauli level.

That qualification still leaves a powerful shortcut: to determine hierarchy membership, researchers can test representatives of affine-equivalence classes rather than every permutation separately.

Existing cryptography results reduce the four-qubit problem to 302 classes. The authors find that exactly five contain permutations in the Clifford hierarchy. This classifies all four-qubit permutation gates by hierarchy membership—not all possible four-qubit quantum gates.

The five qualifying classes were also those closest to affine transformations under the ordering used in an earlier cryptography classification. That observation is suggestive, but the authors could not turn those measures into a rigorous general membership test.

A broader result at the third level

The researchers then combine this permutation classification with previous results about diagonal gates, which change basis-state phases without rearranging the states.

Their target is the semi-Clifford property. A semi-Clifford gate can be converted into a diagonal gate by suitable Clifford operations before and after it. This is a structural simplification, not a claim that the gate itself is Clifford.

Previous theory lets the authors express every third-level gate using Clifford operations surrounding a permutation multiplied by a diagonal gate. They then restrict the diagonal possibilities, group equivalent cases and perform an exhaustive computational search. For four qubits, one reduction leaves 16,384 candidate diagonal classes before further exclusions.

The result goes beyond permutations: every four-qubit gate at the third level is semi-Clifford.

For five qubits, enumerating all affine-equivalence classes is impractical. Instead, the authors use a previous theorem that organizes third-level permutations into a staircase arrangement of Toffoli gates—controlled-controlled bit flips. Further affine reductions leave three non-Clifford permutation classes to examine. Applying the restricted-search strategy establishes that every five-qubit third-level gate is also semi-Clifford.

These conclusions combine mathematical reductions with exhaustive computation. They are not observations from quantum hardware.

Following the states that move

Another approach tracks only the states a permutation moves. A cycle describes states passed around in a loop; a swap is a cycle of length two. The paper represents moved states as columns of a binary matrix, retaining their cycle organization.

For a fixed total number of moved states, the number of affine-equivalence classes eventually stops growing as more qubits are added. Beyond that point, representatives can be constructed by adding controls, making a transformation conditional on additional qubit values.

The authors classify cycle structures moving up to six states, combining computer calculations with proofs that specified families remain in the hierarchy when controls are added.

They also prove a separate sufficient condition for membership. A permutation belongs to the hierarchy if it admits a decomposition into multi-controlled NOT gates in which only one wire serves as both a control and a target. Controls may activate on either zero or one; ordinary, uncontrolled NOT gates are excluded from this mismatch count. This is not a result about ordinary CNOT-only circuits, which are already Clifford.

What remains unresolved

The work does not completely classify the hierarchy. A simple general test for permutation membership remains open, as does whether every six-qubit third-level gate is semi-Clifford. Rapidly growing searches and missing structural results limit extensions.

This briefing uses the arXiv preprint version 3, posted on November 8, 2026. The supplied manuscript states that it was accepted in Quantum on October 20, 2026, so it should not be described as an unreviewed submission.