Characterization of permutation gates in the third level of the Clifford hierarchy

2025/10/06 by Zhiyang He, He, Zhiyang, Luke Robitaille +3 · 1 voice
Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Coding theory and cryptography #FOS: Physical sciences #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.48550/arxiv.2510.04993

openalex publication_date 2025/10/06 · arxiv published 2025/10/06 · arxiv updated 2025/10/06 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/31

Abstract

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.

Citations

• Affine Equivalence in the Clifford Hierarchy
• Quantum Codes with Addressable and Transversal Non-Clifford Gates
• The Clifford hierarchy for one qubit or qudit
• Permutation gates in the third level of the Clifford hierarchy
• Controlled Gates in the Clifford Hierarchy
• Constant-Overhead Magic State Distillation
• Incompressibility and spectral gaps of random circuits
• Simple constructions of linear-depth t-designs and pseudorandom unitaries
• Climbing the Diagonal Clifford Hierarchy
• The Solovay-Kitaev algorithm
• Universal quantum computation with ideal Clifford gates and noisy ancillas
• The Heisenberg Representation of Quantum Computers
• Stabilizer Codes and Quantum Error Correction

Discussions

• Check it out: permutation unitaries in the 3rd level of the Clifford hierarchy whose inverses escape any fixed, finite level of the hierarchy. arxiv.org/abs/2510.04993 Joint work with Luke Robitaille [bsky, 3 points, 0 comments]

Related

• Permutation gates in the third level of the Clifford hierarchy
• Affine Equivalence in the Clifford Hierarchy
• The Clifford hierarchy for one qubit or qudit
• Characterising semi-Clifford gates using algebraic sets
• Clifford Hierarchy Stabilizer Codes: Transversal Non-Clifford Gates and Magic