When is the square root of a Clifford gate a Clifford gate?

Question

Is there any condition for the square root or any rational power of a Clifford gate to be a Clifford gate (generated by $S$, Hadamard $H$, and CNOT)? It can be easily shown that $\sqrt{X}$ is Clifford (because $S=\sqrt{Z}$ is a generator, and powers of $Z$ can be changed into power of $X$ using $H$), but $\sqrt{H}$ and $\sqrt{\mathrm{CNOT}}$ are not-so-obviously non-Clifford. Is there an easy way to tell?

Answer 1

TL;DR A simple sufficient condition is: if the order $r$ of a given Clifford $U$ and the root's degree $n$ are relatively prime, then $U$ has an$^1$ $n$th root.

Let $r$ be the order of $U$, i.e. the smallest positive integer such that $U^r=I$. If $\gcd(n,r)=1$, then there exists a Clifford $V$ such that $V^n=U$. In fact, we can choose $V=U^b$ where $b$ is the multiplicative inverse of $n$ modulo $r$. For example, this criterion shows that $HS$ has a Clifford square root.

In the case $\gcd(n,r)>1$, a Clifford $n$th root may or may not exist. For example, if $U$ is a Pauli operator, then $U=V^2$ where $V=\sqrt{\frac{i}{2}}U+\sqrt{-\frac{i}{2}}I$ is Clifford. However, if $U$ is the Hadamard, then there is no suitable $V$, because Hadamard induces an odd permutation on the axes of the Bloch sphere.

---

^{$^1$ Note that the $n$th root is only well-defined for positive semidefinite operators. Instead of literal interpretation of the question I assume that we would like a criterion that, for a given positive integer $n$ and Clifford $U$, ensures that there exists a Clifford $V$ such that $V^n=U$. Such $V$ will not be unique.}