1.2.1 Extending by linearity

How should we define M⁢(p0p1)M\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)} when MM is an arbitrary operation on a bit? As before, we assume that we know how MM acts on the two possible values of the bit, and we write M⁢[0]M\,[0] for the result of the operation when the bit is zero, and M⁢[1]M\,[1] for the result of the operation when the bit is one. (For the NOT operation, this was precisely what we did in Eq. 1.17.) Let us try to apply the same reasoning as above. With probability p0p_{0}, the bit is zero and so we obtain M⁢[0]M\,[0] by applying the operation MM. With probability p1p_{1}, the bit is one and we obtain instead M⁢[1]M\,[1]. Together, we see that we should define

M⁢(p0p1)=p0⁢M⁢[0]+p1⁢M⁢[1],\displaystyle M\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=p_{0}\,M\,[0]+p_{1}\,M\,[1], (1.25)

where p0⁢M⁢[0]p_{0}\,M\,[0] means that we are multiplying the vector M⁢[0]M\,[0] by the probability p0p_{0}.

Exercise 1.5 (NOT on probabilistic bits).

Show that when MM is the NOT operation then Eq. 1.25 reproduces precisely Eq. 1.22.

Solution. Using Eqs. 1.25 and 1.17,
NOT⁢(p0p1)=p0⁢NOT⁢(10)+p1⁢NOT⁢(01)=p0⁢(01)+p1⁢(10)=(p1p0),\displaystyle\mathrm{NOT}\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=p_{0}\,\mathrm{NOT}\begin{pmatrix}1\\ 0\end{pmatrix}+p_{1}\,\mathrm{NOT}\begin{pmatrix}0\\ 1\end{pmatrix}=p_{0}\begin{pmatrix}0\\ 1\end{pmatrix}+p_{1}\begin{pmatrix}1\\ 0\end{pmatrix}=\begin{pmatrix}p_{1}\\ p_{0}\end{pmatrix},
which is Eq. 1.22.

Using Eq. 1.7, we can also write Eq. 1.25 in the following way:

M⁢(p0⁢[0]+p1⁢[1])=p0⁢M⁢[0]+p1⁢M⁢[1].M\Big{\lparen}p_{0}\,[0]+p_{1}\,[1]\Big{\rparen}=p_{0}\,M\,[0]+p_{1}\,M\,[1]. (1.26)

Note that the difference between the two sides is in the order of operations: on the left-hand side we first take a linear combination and then act with MM, while on the right-hand side we first act with MM and only then take the linear combination. This equation looks very similar to the familiar rule a⁢(b+c)=a⁢b+a⁢ca(b+c)=ab+ac for numbers (the “distributive law”).

If MM is an operation on probabilistic bits that satisfies Eq. 1.26 then we say that MM is linear. Our rule in Eqs. 1.25 and 1.26 for extending MM from bits to probabilistic bits is called extending by linearity. We will often use the same idea also for quantum bits.