Single-qubit Clifford gate: for
DefinitionPRUPermLayer_Supplement_IsCliffordGatep2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandom-unitariesquantum-cryptographyquery-complexity
A single-qubit unitary is a Clifford gate if conjugation by maps each Pauli matrix to a Pauli matrix up to sign: for every there are and with
Up to global phase there are such gates, for example the Hadamard gate and the phase gate . A layer consists of Clifford gates if every is one.
Formalization Note Every global phase is allowed ( is Clifford iff is), so this is the full Clifford group in rather than the 24 phase-free representatives used by the mission's Clifford distribution.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Gates
namespace PRUPermLayer.Supplement
/-- A **single-qubit Clifford gate** (Shen–Zhong, *Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates*, manuscript (STOC 2027 submission; held version sha256 395fcfa3…5bcb), §1.1, p.2 (PDF p.4): "Single-qubit Clifford gates are the
24 gates, up to global phase, that map the Pauli matrices X, Y, Z to Pauli matrices up to sign"):
a unitary `C` on one qubit such that for each `P ∈ {X, Y, Z}` the conjugate `C P C†` equals
`± Q` for some `Q ∈ {X, Y, Z}`.
**Formalization Note** Every global phase is allowed (`c C` is Clifford iff `C` is), so this is
the whole Clifford group of `U(2)`, not the 24 phase-free representatives of the published
`PRUPermLayer.clifford24`. `X, Y, Z` are the published `QAlgorithms.pauliX`, `pauliY`,
`pauliZ`. -/
def IsCliffordGate (C : Matrix.unitaryGroup Bool ℂ) : Prop :=
∀ P ∈ ({QAlgorithms.pauliX, QAlgorithms.pauliY, QAlgorithms.pauliZ} : Set (Matrix Bool Bool ℂ)),
∃ Q ∈ ({QAlgorithms.pauliX, QAlgorithms.pauliY, QAlgorithms.pauliZ} : Set (Matrix Bool Bool ℂ)),
∃ s : ℂ, (s = 1 ∨ s = -1) ∧
(C : Matrix Bool Bool ℂ) * P * star (C : Matrix Bool Bool ℂ) = s • Q
end PRUPermLayer.Supplement
Source
Shen–Zhong, Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates, manuscript (STOC 2027 submission; held version sha256 395fcfa33ec861a7e9c10d88cfcefc2794b77ad1674c02661c9298c5ba565bcb), §1.1, p.2 (PDF p.4)