$\newcommand{\qr}[1]{|#1\rangle}$ I'm reading "Quantum computer science, an introduction," N. David Mermin, Cambridge University Press, 2007. I don't understand Mermin's use of the subscripts in his SWAP operator and in his cNOT operator.
At this point in the book, I'm looking at Cbits as vectors. So $\qr{0}$ is the vector $(1, 0)$ and $\qr{1}$ is $(0, 1)$, assuming I'm working in two dimensions. (These are classical bits, but Mermin in using them as vectors precisely to soon introduce the quantum bits with an already-familiar notation.)
He says: "Perhaps the simplest nontrivial example [of a reversible operation] is the swap (or exchange) operator $S_{ij}$, which simply interchanges the states of Cbits $i$ and $j$: $S_{10} = \qr{xy} = \qr{yx}$."
Mermin then says "Since the swap operator $S_{10}$ interchanges $\qr{01} = \qr{1}_2$ and $\qr{10} = \qr{2}_2$, while leaving $\qr{00} = \qr{0}_2$ and $\qr{11} = \qr{3}_2$ fixed, its matrix in the basis $\qr{0}_2, \qr{1}_2, \qr{2}_2, \qr{3}_2$, is $$S_{10} = S_{01} = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{pmatrix}.$$
I understand this matrix swaps two rows of a vector. For example $$S_{10}\begin{pmatrix}1\\2\\3\\4\end{pmatrix} = \begin{pmatrix}1\\3\\2\\4\end{pmatrix}.$$ But I know this because of the matrix. I couldn't tell what the result would be by just looking at the indices of $S$.
He says "$S_{ij}$ interchanges the states of Cbits $i$ and $j$." So $S_{10}$ must interchange the states of Cbits $1$ and $0$. By Cbit $0$ does he mean the first Cbit from left to right?
I need help understanding this notation better. Can you suggest me exercises so that I can understand this so I can go on with my reading? I gave myself the following exercises.
Exercise 1. He's working with 2 Cbits and there are 4 possible states. They are: $\qr{00}, \qr{01}, \qr{10}, \qr{11}$. How are these vectors written in vector notation? (The following vectors are column-vectors, though I write them as row-vectors to easy my LaTeX writing.) They must be $\qr{00} = (1, 0, 0, 0)$, $\qr{01} = (0, 1, 0, 0)$, ..., $\qr{11} = (0, 0, 0, 1).$
Exercise 2. Still working with 2 Cbits and their 4 possible states, does it make sense to talk about column-vector $(1, 2, 3, 4)$? I say no because with Cbits, this state doesn't exist. The column-vector $(1, 2, 3, 4)$ is the linear combination $1\qr{00} + 2\qr{01} + 3\qr{10} + 4\qr{11}$ which is not possible with Cbits because Cbits do not allow superpositions. Do I make sense here?
Yes, this is correct.
This deals more with linear algebra than computation. A linear transformation $T : V \to W$ (where $V, W$ are vector spaces) is determined by how it maps basis vectors of $V$ to basis vectors of $W$. So we fix a basis for $V$, $\beta = \{ v_{1}, \ldots, v_{n}\}$, and a basis $\gamma = \{ w_{1}, \ldots, w_{k} \}$. The matrix representation of $T$ is just:
$$[T] = [T(v_{1}) \, T(v_{2}) \, \ldots \, T(v_{n})]$$
Where $T(v_i)$ is written with respect to $\gamma$.
Now the vector space you are working in is $\mathbb{F}_{2}^{2} \otimes \mathbb{F}_{2}^{2}$, where $\otimes$ denotes the tensor product. [Note: In quantum computation, you would instead be working in $\mathbb{C}^{2} \otimes \mathbb{C}^{2}$].
Recall that $\qr{0} = (1, 0)$ and $\qr{1} = (0, 1)$. So $|01\rangle = \qr{0} \otimes \qr{1}$. In particular, for any $i, j \in \{0, 1\}$, $|ij\rangle = \qr{i} \otimes \qr{j}$. Review the Tensor product operation to compute these vectors explicitly.
Now the Swap operation on two bits exchanges their values. So we have a linear map $\text{Swap} : \mathbb{F}_{2}^{2} \to \mathbb{F}_{2}^{2}$. So for $\qr{ij}$, we have: $\text{Swap}(\qr{ii}) = \qr{ii}$ for $i \in \{0, 1\}$. And for $i \neq j$, $\qr{ij} = \qr{ji}$ and vice-versa. Does this make sense?
Now suppose I have $n$-bits, which I will represent as $|x_{1}\ldots x_{n}\rangle$ (this is really $\qr{x_{1}} \otimes \qr{x_{2}} \otimes \ldots \qr{x_{n}}$). So for distinct $i, j \in \{1, \ldots, n\}$, $\text{Swap}_{ij} : (\mathbb{F}_{2}^{2})^{\otimes n} \to (\mathbb{F}_{2}^2)^{\otimes n}$ is a linear map (where $(\mathbb{F}_{2}^2)^{\otimes n}$ denotes the tensor product of $\mathbb{F}_{2}^2$ with itself $n$ times). Now $\text{Swap}_{ij}$ just swaps $\qr{x_{i}}$ and $\qr{x_{j}}$ while leaving the other bits fixed.
If we are working over $\mathbb{F}_{2}$, then the coefficients have to be in $\mathbb{F}_{2}$.
If you are looking for a nice set of course notes and exercises, check out Stephen Fenner's course notes.