# The $n$-th root of the NOT gate

I simply can not find material containing facts about the $n$-th root of the NOT gate and it's realization in Q.M. and also in C.M.. Does anyone have material?

A comparison of the $n$-th root NOT gate in Q.M. and C.M. would be nice!

• What is "C.M."? Are you talking about quantum or classical gates? You should make your question more precise. – Norbert Schuch Jul 10 '15 at 15:40
• C.M. = Classical Mechanics, thus I am talking about both. I just need material about the n-th root of the NOT gate in classical and quantum mechanics! Also I added that a comparison between them would be nice. – EpsilonDelta Jul 10 '15 at 15:43
• What do gates have to do with classical mechanics? – Norbert Schuch Jul 10 '15 at 15:55
• There are only odd roots of the classical-logic NOT gate, to my knowledge. Those roots are all the NOT gate, since NOT is self-inverse. – CR Drost Jul 10 '15 at 15:59

This topic seems to me as functions of operators, so I'll explain this issue and will use "n-th root NOT gate" as example.

Any function you apply on the operator - is applied on it's eigenvalues. If the operator is diagonal - all the eigenvalues are on the diagonal and applying the function is simply apply it to any element on the diagonal.

$$A=D=\Sigma_i |i\rangle \lambda_i \langle i |$$
$$f(A)=\Sigma_i |i\rangle f(\lambda_i) \langle i |$$

If the operator is not diagonalised - you should find the unitary matrices $P^{-1}=P^{\dagger}$ such that $A=PDP^{\dagger}$ (all hermitian matrices are unitarily diagonalizable). The logic behind this is to change to basis where the operator is diagonal, apply the function and then move back to the original basis.

In such way - $$f(A)=Pf(D)P^{\dagger}$$

now to your example $$A=\sigma_x= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

the matrix which diagonize it made of it's eigenvectors as columns, such that -

$$P=P^{\dagger}= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$

$$\sigma_x=PDP=\frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$

Thus

$$f(\sigma_x)= \frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1^{\frac{1}{n}} & 0 \\ 0 & (-1)^{\frac{1}{n}} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}=\frac{1}{2} \begin{pmatrix} 1^{\frac{1}{n}}+(-1)^{\frac{1}{n}} & 1^{\frac{1}{n}}-(-1)^{\frac{1}{n}} \\ 1^{\frac{1}{n}}-(-1)^{\frac{1}{n}} & 1^{\frac{1}{n}}+(-1)^{\frac{1}{n}} \end{pmatrix}$$

I'm guessing that by $n^{\text{th}}$ root you mean some gate which if you pass a signal through $n$ of them the output will be identical to the output of the gate you want to "root".

For odd $n$ it's pretty obvious that the classical NOT gate is it's own $n^{\text{th}}$ root. In that an odd number of NOT gates one after the other are identical to a single NOT. I doubt that there is a solution for even $n$ although I have no idea how to go about proving such a thing.

The situation is a bit better in quantum mechanics. The simplest way to do this would be to diagonalise the quantum NOT gate (labelled $\sigma_x)$ as follows (I've assumed you're happy with Dirac notation and basic quantum mechanics):

\begin{align} \sigma_x &= |0\rangle\langle|1| + |1\rangle\langle0|\\ &= \frac{1}{2}\left(|0\rangle + |1\rangle\right)\left(\langle0| + \langle1\right) - \frac{1}{2}\left(|0\rangle - |1\rangle\right)\left(\langle0| - \langle1\right) \end{align}

If we label these new states (which are the eigenstates of $\sigma_x$):

\begin{align} |+\rangle &= \frac{1}{\sqrt{2}}\left(|0\rangle + |1\rangle\right) \\ |-\rangle &= \frac{1}{\sqrt{2}}\left(|0\rangle - |1\rangle\right)\\ \end{align}

Then we can write: \begin{align} \sigma_x = |+\rangle\langle+| - |-\rangle\langle-|\\ \end{align}

Then it is clear that we can come up with $n^{\text{th}}$ roots of $\sigma_x$ like this:

\begin{align} \left(\sigma_x\right)^{\frac{1}{n}} &= 1^{\frac{1}{n}}|+\rangle\langle+| + (-1)^{\frac{1}{n}} |-\rangle\langle-|\\ \end{align}

Given that we can use any of the $n^{\text{th}}$ roots of $1$ and any of those of $-1$ we can construct $n^2$ roots like this. Note that I've assumed you're talking about the not gate which acts on a qubit in a computational basis state to flip it to the other one.

Sorry I couldn't be more helpful about the classical case and feel free to ask any questions you like.

• This is exactly what I was going to say, except mine would have done the $|+\rangle$, $|-\rangle$ lifting with the Hadamard gate: NOT is the Pauli $\sigma_x$ which is $H^\dagger \sigma_z H$, since $H H^\dagger = 1$ this is sufficient to give the $n$th root as $H^\dagger \sigma_z^{1/n} H$, and you can use any of $n$ roots of $\sqrt{-1}$ to get $n$ different roots of NOT. – CR Drost Jul 10 '15 at 15:53
• Note that since gates are only defined up to a phase, there are in fact only $n$ roots of the quantum not gate. – Norbert Schuch Jul 10 '15 at 15:54
• @NorbertSchuch: Are you sure that a phase is irrelevant? I am thinking of cases where we can spatially separate the $|0\rangle$ and $|1\rangle$ components into two channels, apply the gate to one channel and recombine them. In this case it is possible to apply a unitary to only a single component of the wave-function so the phase of the gate will matter (i.e. we use the effective gate $|0\rangle\langle0| +U|1\rangle\langle1|$). I could be totally mistaken though... – or1426 Jul 10 '15 at 16:21
• @or1426 The phase is irrelevant if you gate acts within a tensor product (i.e., as $I\otimes \sigma_x$). In the setup you describe, it acts as $I\oplus\sigma_x$, i.e., a CNOT gate. In that case, the phase matter. However, I would not call $\sigma_x$ a gate in that case (since gates act on tensor products). – Norbert Schuch Jul 11 '15 at 16:36

The NOT gate can be written as $$\sigma_x \propto \exp[i\pi/2\,\sigma_x]$$ (up to an irrelevant global phase). Its roots are therefore of the form $$\exp[i\phi\,\sigma_x] = \cos(\phi)\,I + i\sin(\phi)\,\sigma_x$$ with $n\phi = \pi/2 + 2\pi k$ with $k\in\mathbb N$.