2.5 The square root of NOT

Now that we have poked our heads into the quantum world, let us see how quantum interference challenges conventional logic. Consider a following task: design a logic gate that operates on a single bit and such that when it is followed by another, identical, logic gate the output is always the negation of the input. Let us call this logic gate the square root of \texttt{NOT}, or \sqrt{\texttt{NOT}}.

A simple check, such as an attempt to construct a truth table, should persuade you that there is no such operation in logic. It may seem reasonable to argue that since there is no such operation in logic, \sqrt{\texttt{NOT}} is impossible. But it does exist! Experimental physicists routinely construct such “impossible” gates in their laboratories. It is a physically admissible operation described by the unitary matrix32 \sqrt{\texttt{NOT}} = \frac12 \begin{bmatrix} 1+i & 1-i \\1-i&1+i \end{bmatrix} = \frac1{\sqrt2} \begin{bmatrix} e^{i\frac{\pi}{4}} & e^{-i\frac{\pi}{4}} \\e^{-i\frac{\pi}{4}} & e^{i\frac{\pi}{4}} \end{bmatrix}. Indeed, \frac12 \begin{bmatrix} 1+i & 1-i \\1-i & 1+i \end{bmatrix} \frac12 \begin{bmatrix} 1+i & 1-i \\1-i & 1+i \end{bmatrix} = \begin{bmatrix} 0&1 \\1&0 \end{bmatrix}.

We could also step through the circuit diagram and follow the evolution of the state vector:

Or, if you prefer to work with column vectors and matrices, you can write the two consecutive application of \sqrt{\texttt{NOT}} to state |0\rangle as \begin{bmatrix}0\\1\end{bmatrix} \,\longleftarrow\!\!\!\vert\,\, \frac{1}{\sqrt 2} \begin{bmatrix} e^{i\frac{\pi}{4}} \\e^{-i\frac{\pi}{4}} \end{bmatrix} \,\longleftarrow\!\!\!\vert\,\, \begin{bmatrix}1\\0\end{bmatrix} (following a well established convention, the above should be read from right to left)33, where each \longleftarrow\!\!\!\vert denotes multiplication by \frac1{\sqrt2}\begin{bmatrix}e^{i\frac{\pi}{4}} & e^{-i\frac{\pi}{4}}\\e^{-i\frac{\pi}{4}} & e^{i\frac{\pi}{4}}\end{bmatrix}.

One way or another, quantum theory explains the behaviour of \sqrt{\texttt{NOT}}, and so, reassured by the physical experiments34 that corroborate this theory, logicians are now entitled to propose a new logical operation \sqrt{\texttt{NOT}}. Why? Because a faithful physical model for it exists in nature!

  1. There are infinitely many unitary operations that act as the square root of \texttt{NOT}.↩︎

  2. Just remember that circuits diagrams are read from left to right, and vector and matrix operations go from right to left.↩︎

  3. We discuss this in more detail in [Appendix:!!to-do!! Physics against logic, via beamsplitters].↩︎