Spectral theorem for Pauli matrices

Question

Let $ P $ be a Pauli matrix. Pauli matrices are normal. So by the spectral theorem $ P $ can be written as $$ P=VDV^{-1} $$ for $ V $ unitary and $ D $ diagonal (in other words $ P $ is unitarily diagonalizable). Can we conclude that $ D $ must be in the Pauli group? Moreover, can we conclude that $ V $ must be in the Clifford group?

For certain examples of $ P $ and certain spectral decompositions this is obviously true. For example $$ X=HZH $$ here it is indeed the case that $ Z $ is a Pauli and $ H $ is in the Clifford group.

Summary:

The answer by DaftWullie shows that every Pauli matrix is diagonalizable by a Clifford gate $ V $. This implies (indeed is equivalent to) the fact that the diagonalization of a Pauli matrix is always another Pauli matrix.

Discussion with Bebotron shows that there is no uniqueness to this diagonalizing gate $ V $. A given Pauli matrix can be diagonalized by both Clifford and non Clifford gates. And multiple different Clifford gates can diagonalize the same Pauli. DaftWullie comments further on the extraordinary non-uniqueness of the diagonalizing gate $ V $.

Answer 1

Consider a member of the Pauli group on $N$ qubits. I'm going to write this (up to a possible $\pm1,\pm i$ multiplier) as $$ P=X_xZ_z $$ where $x,z\in\{0,1\}^N$ denote the places where the $X$ and $Z$ operators lie. Let $y$ be $x$ OR $z$ applied bitwise (and I really mean OR, not XOR). There is always a unitary that maps this Pauli to $Z_y$, which is the diagonal Pauli you wanted. To see this, take each site $i$. If $x_i=0$, do nothing: the qubit is $Z^{y_i}$. If $x_i=1,z_i=0$, apply Hadamard to qubit $i$. This transforms $X$ to $Z$ (and is in the Clifford group). If $x_i=z_i=1$, the qubit $i$ has a $Y$. Apply the gate $H_Y=(Y+Z)/\sqrt{2}$. In the same way that Hadamard, $(X+Z)/\sqrt{2}$ exchanges $X$ and $Z$, this exchanges $Y$ and $Z$, as required.

Now all we have to do is verify that $H_Y$ is Clifford. That means checking that its action on each of the 3 single-qubit Pauli matrices returns a Pauli matrix (up to phases). It was already constructed to do this on $Z$ and $Y$. We just have to check $X$. But $H_Y$ and $X$ anticommute, so $H_YXH_Y=-X$. Thus, $H_Y$ is Clifford.

What I have just proven is that there always exists a unitary transformation that satisfies your conditions. Your question specifies must the unitary be of that form? The simple answer is no. As soon as $N>1$, your eigenspace has degeneracy. This means that, in addition to the unitary I have constructed, you can apply any unitary that preserves those two spaces. These can certainly be non-Clifford, and can indeed be universal for quantum computation.

Answer 2

That is correct, that is the basic definition of the Clifford group, a set of unitaries that normalize the Pauli group. To rephrase from the link, the Clifford group is

$$C_n = \{V \in U_{2^n} | VP_nV^{\dagger}=P_n\}$$

where $P_n$ is the $n$-qubit Pauli group.

Edit: Finally note that if we try using $T$ gates,

$$TXT^{\dagger}=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}1&0\\0&e^{-i\pi/4}\end{pmatrix}\\ =\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}\begin{pmatrix}0&e^{-i\pi/4}\\1&0\end{pmatrix}\\=\begin{pmatrix}0&e^{-i\pi/4}\\e^{i\pi/4}&0\end{pmatrix}$$

which is not a Pauli matrix, therefore $T$ gate is not Clifford.