3.1.5 SWAP operation

Now that we know how to manipulate individual probabilistic bits, we would also like to apply operations on several bits at a time. One of the simplest such operations is the SWAP\mathrm{SWAP} operation that interchanges two bits:

SWAP⁢[00]\displaystyle\mathrm{SWAP}\,[00] =[00],\displaystyle=[00],
SWAP⁢[01]\displaystyle\mathrm{SWAP}\,[01] =[10],\displaystyle=[10],
SWAP⁢[10]\displaystyle\mathrm{SWAP}\,[10] =[01],\displaystyle=[01],
SWAP⁢[11]\displaystyle\mathrm{SWAP}\,[11] =[11].\displaystyle=[11].

SWAP\mathrm{SWAP} effectively amounts to exchanging the strings [01][01] and [10][10] while leaving the other two strings alone. The above equations can be written more concisely as follows:

SWAP⁢[a,b]=[b,a],\mathrm{SWAP}\,[a,b]=[b,a], (3.18)

for all a,b∈{0,1}a,b\in\{0,1\}, where we use a comma to separate the two bits. As usual, we can extend SWAP\mathrm{SWAP} from deterministic to probabilistic bits by linearity:

SWAP(\displaystyle\mathrm{SWAP}\,\bigl{(} p00[00]+p01[01]+p10[10]+p11[11])\displaystyle p_{00}[00]+p_{01}[01]+p_{10}[10]+p_{11}[11]\bigr{)}
=\displaystyle={} p00⁢[00]+p01⁢[10]+p10⁢[01]+p11⁢[11]\displaystyle p_{00}[00]+p_{01}[10]+p_{10}[01]+p_{11}[11]
=\displaystyle={} p00⁢[00]+p10⁢[01]+p01⁢[10]+p11⁢[11].\displaystyle p_{00}[00]+p_{10}[01]+p_{01}[10]+p_{11}[11].
Exercise 3.3 ( SWAP\mathrm{SWAP} in the 4-vector notation (optional) ).

Write down the action of SWAP\mathrm{SWAP} on two probabilistic bits in the 4-vector notation.

Solution.
SWAP⁢(p00p01p10p11)=(p00p10p01p11).\displaystyle\mathrm{SWAP}\begin{pmatrix}p_{00}\\ p_{01}\\ p_{10}\\ p_{11}\end{pmatrix}=\begin{pmatrix}p_{00}\\ p_{10}\\ p_{01}\\ p_{11}\end{pmatrix}.