DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2026.2

Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy

Authors: Zhiyang He, Luke Robitaille, and Xinyu Tan

Published in: LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)

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.

Cite as

Zhiyang He, Luke Robitaille, and Xinyu 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 389, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.TQC.2026.2,
  author =	{He, Zhiyang and Robitaille, Luke and Tan, Xinyu},
  title =	{{Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy}},
  booktitle =	{21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-439-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{389},
  editor =	{Arnon, Rotem and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.2},
  URN =		{urn:nbn:de:0030-drops-272997},
  doi =		{10.4230/LIPIcs.TQC.2026.2},
  annote =	{Keywords: Quantum fault-tolerance, Clifford hierarchy, permutation gates}
}

Search Results

Documents authored by Robitaille, Luke

Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy

Abstract

Cite as

Thanks for your feedback!

Could not send message