1.2.2 Random operations

Note that, in our derivation of Eq. 1.25, we did not in fact assume that $M\,[0]$ and $M\,[1]$ were again one of the two deterministic states $[0]$ or $[1]$ of a bit (even though this happened to be the case for the NOT operation). This means that Eq. 1.25 works just as well when $M\,[0]$ or $M\,[1]$ are probabilistic bits! In this case we say that $M$ is a random operation.

One of the simplest examples of a random operation is as follows. Imagine that you encode $[0]$ by placing a pencil horizontally on a table, and $[1]$ by balancing it vertically. If you gently hit the table with your hand, the pencil might fall down, changing its state from $[1]$ to $[0]$ . However, if it was already laying down, its state $[0]$ will not change. Thus hitting the table probabilistically resets the pencil’s state to $[0]$ ; the harder you hit, the more likely you are to reset it.

Mathematically, probabilistic reset is described by an operation $R(r)$ defined as

R(r)\,[0]=[0]=\begin{pmatrix}1\\ 0\end{pmatrix},\qquad R(r)\,[1]=r\,[0]+(1-r)\,[1]=\begin{pmatrix}r\\ 1-r\end{pmatrix},

(1.27)

where $r\in[0,1]$ is the reset probability. You can visualize the action of this operation as follows:

By linearity, we can extend this operation to all states:

	$\displaystyle R(r)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}$	$\displaystyle=p_{0}\,R(r)\,[0]+p_{1}\,R(r)\,[1]$
		$\displaystyle=p_{0}\,\begin{pmatrix}1\\ 0\end{pmatrix}+p_{1}\,\begin{pmatrix}r\\ 1-r\end{pmatrix}=\begin{pmatrix}p_{0}+p_{1}r\\ p_{1}(1-r)\end{pmatrix}.$

As a special case of this equation, note that $R(0)$ does not change the state at all while $R(1)$ resets any state to $[0]$ .

Another interesting example of a random operation is the probabilistic flip operation $F(f)$ that flips the input bit with probability $f$ and leaves it alone with probability $1-f$ :

F(f)\,[0]=(1-f)\,[0]+f\,[1],\qquad F(f)\,[1]=f\,[0]+(1-f)\,[1],

(1.28)

where $f\in[0,1]$ is the flip probability. More intuitively, imagine that $[0]$ and $[1]$ represent two states of a light switch on a wall. If you throw a pillow at the switch, you will successfully hit and flip it only with probability $f$ , and with probability $1-f$ it will remain unchanged. You can visualize the action of $F(f)$ as follows:

The next exercise will help you to get more familiar with the probabilistic flip operation.

Exercise 1.6 (Probabilistic flip).

Recall that $F(f)$ denotes the probabilistic flip operation from Eq. 1.28.

1.

Write down $F(f)\,[0]$ and $F(f)\,[1]$ as vectors.
2.

For what value of $f$ does $F(f)$ act as $\mathrm{NOT}$ ? How can we prepare a probabilistic bit in an arbitrary state $\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}$ from $[0]$ by using $F$ ?
3.

Extend $F(f)$ by linearity to probabilistic bits by computing $F(f)\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ .
4.

Let $\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}$ be an arbitrary probability distribution. Show that $F(1/2)\,\bigl{(}\begin{smallmatrix}p_{0}\\ p_{1}\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}1/2\\ 1/2\end{smallmatrix}\bigr{)}$ .

Solution.

Using the definition of $F(f)$ in Eq. 1.28,

	$\displaystyle F(f)\,[0]$	$\displaystyle=(1-f)\,\bigl{(}\begin{smallmatrix}1\\ 0\end{smallmatrix}\bigr{)}+f\,\bigl{(}\begin{smallmatrix}0\\ 1\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}1-f\\ f\end{smallmatrix}\bigr{)},$
	$\displaystyle F(f)\,[1]$	$\displaystyle=f\,\bigl{(}\begin{smallmatrix}1\\ 0\end{smallmatrix}\bigr{)}+(1-f)\,\bigl{(}\begin{smallmatrix}0\\ 1\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}f\\ 1-f\end{smallmatrix}\bigr{)}.$

2.

$F(f)$ flips the bit with certainty when $f=1$ , so $\mathrm{NOT}=F(1)$ . To prepare an arbitrary state $\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}$ from $[0]$ we need to choose $f=1-p$ . Indeed, we see from the first equation above that

$\displaystyle F(1-p)\,[0]=\begin{pmatrix}1-(1-p)\\ 1-p\end{pmatrix}=\begin{pmatrix}p\\ 1-p\end{pmatrix}.$

Following Eq. 1.25,

\displaystyle F(f)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=p_{0}\begin{pmatrix}1-f\\ f\end{pmatrix}+p_{1}\begin{pmatrix}f\\ 1-f\end{pmatrix}=\begin{pmatrix}p_{0}(1-f)+p_{1}f\\ p_{0}f+p_{1}(1-f)\end{pmatrix}.

4.

Substituting $f=1/2$ in the previous equation we get

$F(1/2)\,\begin{pmatrix}p_{0}\\ p_{1}\end{pmatrix}=\begin{pmatrix}p_{0}/2+p_{1}/2\\ p_{0}/2+p_{1}/2\end{pmatrix}=\frac{1}{2}\begin{pmatrix}p_{0}+p_{1}\\ p_{0}+p_{1}\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1\\ 1\end{pmatrix}.$

The last part of this exercise shows that $F(1/2)$ always prepares the uniform distribution, no matter the input distribution. This can be used for simulating the toss of an unbiased coin. In fact, in the next exercise, you will show that by carefully adjusting the flip probability $f$ you can also use $F(f)$ to change the bias of a given coin.

Homework 1.3 (Chocolate coin).

Today is Bob’s birthday! Since he likes chocolate, Alice decides to make a chocolate coin for him. To make it more special, the shape of the coin should be such that if you spin it on the table, it would land on with probability $q=5/15$ that represents Bob’s birthday, May 15th. After experimenting with several different shapes, Alice manages to produce a chocolate coin with the right probability. Very excited, she leaves it on the table and runs to the shop to buy a nice birthday card.

Unfortunately, when she returns, Alice realizes that the coin was left in the sun and its edge has melted. After trying it out, Alice determines that the new probability of is $p=4/15$ . Since there is no time left to fix the problem, Alice writes on the birthday card that once the coin has landed, Bob should flip it around with probability $f$ , and only then he will observe with the right probability $q$ . Help Alice to determine the right value of $f$ .

Hint: The quantities $p$ , $q$ , and $f$ should satisfy $F(f)\,\bigl{(}\begin{smallmatrix}p\\ 1-p\end{smallmatrix}\bigr{)}=\bigl{(}\begin{smallmatrix}q\\ 1-q\end{smallmatrix}\bigr{)}$ .

Hack.

Recall from your solution to 1.6 that

\displaystyle F(f)\,\begin{pmatrix}p\\ 1-p\end{pmatrix}=p\begin{pmatrix}1-f\\ f\end{pmatrix}+(1-p)\begin{pmatrix}f\\ 1-f\end{pmatrix}=\begin{pmatrix}p(1-f)+(1-p)f\\ pf+(1-p)(1-f)\end{pmatrix}.

We want this to be equal to $\bigl{(}\begin{smallmatrix}q\\ 1-q\end{smallmatrix}\bigr{)}$ , so we get

	$\displaystyle p(1-f)+(1-p)f$	$\displaystyle=q,$
	$\displaystyle pf+(1-p)(1-f)$	$\displaystyle=1-q.$

Solving any of the two equations for $f$ , we find

f=\frac{q-p}{1-2p}.

Substituting $p=4/15$ and $q=5/15$ , we get $f=1/7$ .

Exercise 1.7 (Flip from reset and NOT (optional and challenging)).

How can you build $F(f)$ using the $R(r)$ and $\mathrm{NOT}$ operations?

Solution.

We distinguish two cases:

•

$\frac{1}{2}\leq f\leq 1$ : In this case, $0\leq\frac{1-f}{f}\leq 1$ . We claim that the flip operation $F(f)$ can be built by first applying $R(\tfrac{1-f}{f})$ , then $\mathrm{NOT}$ , and finally $R(1-f)$ . Indeed:

\displaystyle R(1-f)\,\mathrm{NOT}\,R(\tfrac{1-f}{f})\,[0]=R(1-f)\,\mathrm{NOT% }\,[0]=R(1-f)\,[1]=(1-f)\,[0]+f\,[1]

and

	$\displaystyle R(1-f)\,\mathrm{NOT}\,R(\tfrac{1-f}{f})\,[1]$	$\displaystyle=R(1-f)\,\mathrm{NOT}\,\Bigl{(}\tfrac{1-f}{f}\,[0]+(1-\tfrac{1-f}% {f})\,[1]\Bigr{)}$
		$\displaystyle=R(1-f)\,\Bigl{(}(1-\tfrac{1-f}{f})\,[0]+\tfrac{1-f}{f}\,[1]\Bigr% {)}$
		$\displaystyle=(1-\tfrac{1-f}{f})\,[0]+\tfrac{1-f}{f}\left((1-f)\,[0]+f\,[1]\right)$
		$\displaystyle=f\,[0]+(1-f)\,[1].$

•

$0\leq f\leq\frac{1}{2}$ : This case can be reduced to the first, since $F(f)$ is the same as first applying $F(1-f)$ and then $\mathrm{NOT}$ .