1.2 Operations on a probabilistic bit

Once we have represented bits of information by vectors, we can represent operations on these bits by linear transformations and use tools from linear algebra. For example, consider the operation that exchanges “heads” and “tails” of a donkey coin:

We will denote this operation by $\mathrm{NOT}$ and write it down mathematically as follows:

\mathrm{NOT}\;\vbox{\hbox{\includegraphics[width=30.0pt]{figs/0.png}}}=\vbox{% \hbox{\includegraphics[width=30.0pt]{figs/1.png}}},\qquad\mathrm{NOT}\;\vbox{% \hbox{\includegraphics[width=30.0pt]{figs/1.png}}}=\vbox{\hbox{% \includegraphics[width=30.0pt]{figs/0.png}}}.

,NOT⁢

.\mathrm{NOT}\;\vbox{\hbox{\includegraphics[width=30.0pt]{figs/0.png}}}=\vbox{% \hbox{\includegraphics[width=30.0pt]{figs/1.png}}},\qquad\mathrm{NOT}\;\vbox{% \hbox{\includegraphics[width=30.0pt]{figs/1.png}}}=\vbox{\hbox{% \includegraphics[width=30.0pt]{figs/0.png}}}. (1.16)

Using the conventions from Eq. 1.6, we can also write

\mathrm{NOT}\,[0]=[1],\qquad\mathrm{NOT}\,[1]=[0].

(1.17)

Note that we are writing $\mathrm{NOT}\,p$ as an abbreviation to $\mathrm{NOT}(p)$ – both simply mean that the operation $\mathrm{NOT}$ acts on a vector $p$ .¹¹ 1 We could also write $\mathrm{NOT}\cdot p$ since this action actually corresponds to matrix-vector multiplication. We will generally write operations with capital letters to distinguish them from numbers and vectors.

Recall from Eq. 1.6 that the vectors $[0]$ and $[1]$ represent the deterministic states $0$ and $1$ of a probabilistic bit. Since the $\mathrm{NOT}$ operation exchanges these two vectors, it negates the value of the bit. This is precisely why we called it “NOT” – it represents the logical negation! One simple application of $\mathrm{NOT}$ is to enter some data in your computer. If all bits of your computer are initially set to $0$ , you can change some of them to $1$ to enter data – this is often the first step of a computation.

How should we define the NOT operation on a probabilistic bit $p=\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ ? With probability $p_{0}$ , the bit is zero and will get flipped to a one. With probability $p_{1}$ , the bit is one and will get flipped to a zero. Thus, the effect of the NOT operation on a probabilistic bit is simply

\displaystyle\mathrm{NOT}\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=\begin{pmatrix}p_{1}\\ p_{0}\end{pmatrix}.

(1.22)

In particular, this recovers Eq. 1.17 when $p_{0}=1$ (and $p_{1}=0$ ) or $p_{0}=0$ (and $p_{1}=1$ ). You can intuitively think of the NOT operation and Eq. 1.22 as follows: if you imagine a probabilistic bit as a coin that you have tossed but have not looked at yet, then the NOT operation corresponds to turning the coin around (again, without looking at it).

Exercise 1.4 (Visualizing the NOT operation).

Recall from Fig. 1.2 that all possible states of a probabilistic bit correspond to a line segment. Let us try to visualize how the $\mathrm{NOT}$ operation transforms this line segment.

1.

Take an arbitrary²² 2 When we say ‘arbitrary’, we mean that your calculation must work for any choice of $p_{0}$ and $p_{1}$ . It is often best to write all the steps, including your final answer, in terms of $p_{0}$ and $p_{1}$ , treating them as unknown numbers. point with coordinates $(p_{0},p_{1})$ on this segment. Where is it sent to by the $\mathrm{NOT}$ operation?
2.

Where are the two endpoints of the line segment sent to?
3.

Is there any point on the line segment that is sent to itself?

Solution.

1.

Note from Eq. 1.22 that the point $(p_{0},p_{1})$ is sent to $(p_{1},p_{0})$ . In other words, the two coordinates of the point are exchanged. Here is an example of how this looks like:

You can thus think of the $\mathrm{NOT}$ operation as the reflection around the dashed line that goes right in the middle between the two coordinate axes.
2.

According to Eq. 1.6, the two end-points $(1,0)$ and $(0,1)$ of the line segment correspond to the two deterministic states $[0]$ and $[1]$ . Recall from Eq. 1.17 that the $\mathrm{NOT}$ operation exchanges them.
3.

A point with coordinates $(p_{0},p_{1})$ remains fixed by the $\mathrm{NOT}$ operation if $(p_{0},p_{1})=(p_{1},p_{0})$ , meaning that $p_{0}=p_{1}$ . Since $p_{0}+p_{1}=1$ , we find that $p_{0}=p_{1}=1/2$ which corresponds to the point $(1/2,1/2)$ . This is the only point that remains fixed.