2026-08-25T11:01:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27299 2026-08-25T07:42:36Z ddc:004 open_access

Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy He, Zhiyang Robitaille, Luke Tan, Xinyu Quantum fault-tolerance Clifford hierarchy permutation gates The Clifford hierarchy is a fundamental structure in quantum computation whose mathematical properties are not fully understood. In this work, we characterize permutation gates - unitaries which permute the 2ⁿ basis states - in the third level of the hierarchy. We prove that any permutation gate in the third level must be a product of Toffoli gates in what we define as staircase form, up to left and right multiplications by Clifford permutations. We then present necessary and sufficient conditions for a staircase form permutation gate to be in the third level of the Clifford hierarchy. As a corollary, we construct a family of non-semi-Clifford permutation gates {U_k}_{k ≥ 3} in staircase form such that each U_k is in the third level but its inverse is not in the k-th level. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhiyang He and Luke Robitaille and Xinyu Tan 2026 Is Part Of LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2026.2 urn:nbn:de:0030-drops-272997 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode