1
$\begingroup$

$\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?

$\endgroup$
2
  • $\begingroup$ Can you post the equations here, rather than as an external link? My ad blocker is preventing me from opening the external link. $\endgroup$ – ml0105 Dec 31 '17 at 4:55
  • 1
    $\begingroup$ @ml0105, rewrote the question turning that external link unnecessary. Thanks for your interest in the question. $\endgroup$ – R. Chopin Jan 2 '18 at 12:07
0
$\begingroup$

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?

Yes, this is correct.

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$.

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}$].

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).$

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.

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?

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.