## Quantum Country exercise 16

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 16. Show that the inverse of the Toffoli gate is the Toffoli gate itself.

Answer: With input states $\vert x \rangle$, $\vert y \rangle$, and $\vert z \rangle$ the output states of the Toffoli gate are $\vert x \rangle$, $\vert y \rangle$, and $\vert z \oplus \left( x \wedge y \right) \rangle$.

If those output states are used as the input states to a second Toffoli gate, the first two output states will again be $\vert x \rangle$ and $\vert y \rangle$. The third output state will be $\vert \left[ z \oplus \left( x \wedge y \right) \right] \oplus \left( x \wedge y \right) \rangle$. We have

$\left[ z \oplus \left( x \wedge y \right) \right] \oplus \left( x \wedge y \right) = z \oplus \left[ \left( x \wedge y \right) \oplus \left( x \wedge y \right) \right]$

The expression $x \wedge y$ will have either the value 0 or the value 1. If it has the value 0 then we have

$z \oplus \left[ \left( x \wedge y \right) \oplus \left( x \wedge y \right) \right] = z \oplus \left( 0 \oplus 0 \right) = z \oplus 0 = z$

If it has the value 1 then we have

$z \oplus \left[ \left( x \wedge y \right) \oplus \left( x \wedge y \right) \right] = z \oplus \left( 1 \oplus 1 \right) = z \oplus 0 = z$

We therefore have

$\left[ z \oplus \left( x \wedge y \right) \right] \oplus \left( x \wedge y \right) = z$

so that the third output state from the second Toffoli gate is simply $\vert z \rangle$. Since the first and second output states from the second Toffoli gate were $\vert x \rangle$ and $\vert y \rangle$, the output states of the second Toffoli gate are the same as the input states of the first Toffoli gate. The Toffoli gate therefore acts as its own inverse.

## Quantum Country exercise 15

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 15. Find a way of implementing a NAND gate using just a single Toffoli gate and no other quantum gates.

Answer: As described in the previous exercise, a Toffoli gate with inputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 1 \rangle$ acts as a NAND gate producing the target output $\vert 1 \oplus \left( x \wedge y \right) \rangle = \vert \neg \left( x \wedge y \right) \rangle$.

## Quantum Country exercise 14

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 14. Describe a quantum circuit that can compute the NAND gate, where the NAND of two bits $x$ and $y$ is the NOT of $x \wedge y$.

Answer: The Toffoli gate with inputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 0 \rangle$ produces the outputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 0 \oplus \left( x \wedge y \right) \rangle = \vert x \wedge y \rangle$. It thus functions as an AND gate.

One way to produce a NAND gate is thus to put the target output $\vert x \wedge y \rangle$ through the X gate, which will NOT the value.

A second, and simpler, way is to use the input value $\vert 1 \rangle$ as the target qubit $\vert z \rangle$ to the Toffoli gate. This will produce the target output $\vert 1 \oplus \left( x \wedge y \right) \rangle$. When $x \wedge y = 0$ then we have $1 \oplus 0 = 1$, and when $x \wedge y = 1$ we have $1 \oplus 1 = 0$. Thus $1 \oplus \left( x \wedge y \right)$ is equivalent to $\neg \left( x \wedge y \right)$.

Therefore a Toffoli gate with inputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 1 \rangle$ acts as a NAND gate producing the target output $\vert \neg \left( x \wedge y \right) \rangle$.

## Quantum Country exercise 13

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 13. Show that the product $UV$ of two unitary matrices $U$ and $V$ is itself a unitary matrix.

Answer: Since $U$ and $V$ are unitary matrices we have $U^\dagger U = I$ and $V^\dagger V = I$.

Now consider the product $UV$. We have

$\left( UV \right)^\dagger \left( UV \right) = \left( V^\dagger U^\dagger \right) \left( UV \right)$

$= V^\dagger \left( U^\dagger U \right) V = V^\dagger I V = V^\dagger V = I$.

Since $\left( UV \right)^\dagger \left( UV \right) = I$ the product matrix $UV$ is unitary. Thus the product $UV$ of two unitary matrices $U$ and $V$ is itself a unitary matrix.

## Quantum Country exercise 12

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 12. Show that the inverse of the CNOT gate is just the CNOT gate.

Answer: Since CNOT is a quantum gate it is equivalent to some unitary matrix $M$, and the result of applying it to a quantum state $\vert \psi \rangle$ is the product $M \vert \psi \rangle$. The result of applying CNOT twice is then given by $M \left( M \vert \psi \rangle \right) = \left ( MM \right) \vert \psi \rangle = Q \vert \psi \rangle$ where $Q = MM$.

If the quantum state $\vert \psi \rangle = \alpha \vert 00 \rangle + \beta \vert 01 \rangle + \gamma \vert 10 \rangle + \delta \vert 11 \rangle$, then applying CNOT twice to $\vert \psi \rangle$ produces a final state

$Q \vert \psi \rangle = Q \left( \alpha \vert 00 \rangle + \beta \vert 01 \rangle + \gamma \vert 10 \rangle + \delta \vert 11 \rangle \right)$

$= Q \left( \alpha \vert 00 \rangle \right) + Q \left( \beta \vert 01 \rangle \right) + Q \left( \gamma \vert 10 \rangle \right) + Q \left( \delta \vert 11 \rangle \right)$

$= \alpha Q \vert 00 \rangle + \beta Q \vert 01 \rangle + \gamma Q \vert 10 \rangle + \delta Q \vert 11 \rangle$

As discussed in the text, if we take the result of CNOT and apply CNOT again, this takes  $\vert 00 \rangle$ to $\vert 00 \rangle$ and then to $\vert 00 \rangle$, because CNOT does not do anything when the value of the control bit is zero. Similarly applying CNOT twice takes $\vert 01 \rangle$ to $\vert 01 \rangle$ and then to $\vert 01 \rangle$ again.

Applying CNOT twice to $\vert 10 \rangle$ produces $\vert 11 \rangle$ upon applying the first CNOT, and then applying CNOT again produces $\vert 10 \rangle$, the same as the starting state. Similarly, applying CNOT twice to $\vert 11 \rangle$ produces $\vert 10 \rangle$ upon applying the first CNOT and then $\vert 11 \rangle$ upon applying the second, the same state as the starting state.

So applying CNOT twice to each of the four basis states leaves each of those states unchanged. Stated another way, we have

$Q \vert 00 \rangle = \vert 00 \rangle$

$Q \vert 01 \rangle = \vert 01 \rangle$

$Q \vert 10 \rangle = \vert 10 \rangle$

$Q \vert 11 \rangle = \vert 11 \rangle$

We thus have

$Q \vert \psi \rangle = \alpha Q \vert 00 \rangle + \beta Q \vert 01 \rangle + \gamma Q \vert 10 \rangle + \delta Q \vert 11 \rangle$

$= \alpha \vert 00 \rangle + \beta \vert 01 \rangle + \gamma \vert 10 \rangle + \delta \vert 11 \rangle = \vert \psi \rangle$

Since $Q \vert \psi \rangle = \vert \psi \rangle$ for any state $\vert \psi \rangle$ we have $Q = I$, and since $Q = MM$ where $M$ is the matrix corresponding to applying the CNOT gate twice, we have $MM = I$. Thus the CNOT gate is its own inverse.

## Quantum Country exercise 11

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 11. Find single-qubit states $\vert a \rangle$ and $\vert b \rangle$ such that applying the CNOT gate to the combined state $\vert ab \rangle$ changes the first qubit, i.e., the control qubit.

Answer: This is a placeholder for when I get around to looking at this problem in depth.

## Quantum Country exercise 10

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 10. Show that $M \vert e_k \rangle$ is the $k$th column of the matrix $M$ and that $\langle e_j \vert M \vert e_k \rangle$ is the $jk$th entry of $M$.

Answer: The product of the matrix $M$ and the vector $\vert e_k \rangle$ is a vector, with the $j$th entry of that vector being the inner product of the $j$th row of $M$ with $\vert e_k \rangle$:

$\left( M \vert e_k \rangle \right)_j = \sum_l M_{jl} \vert e_k \rangle_l$

We then have

$\sum_l M_{jl} \vert e_k \rangle_l = M_{jk} \vert e_k \rangle_k + \sum_{l \ne k} M_{jl} \vert e_k \rangle_l$

But by the definition of $\vert e_k \rangle$ we have $\vert e_k \rangle_k = 1$ and $\vert e_k \rangle_l = 0$ for $l \ne k$. So the above reduces to

$M_{jk} \vert e_k \rangle_k + \sum_{l \ne k} M_{jl} \vert e_k \rangle_l = M_{jk} \cdot 1 + \sum_{l \ne k} M_{lj} \cdot 0 = M_{jk}$

So $\left( M \vert e_k \rangle \right)_j = M_{jk}$ for all $j$, which means that $M \vert e_k \rangle$ is the $k$th column of $M$.

We now consider the product $\langle e_j \vert M \vert e_k \rangle$ for some $j$. This is the inner product of the vector $\langle e_j \vert$ with the vector $\vert M \vert e_k \rangle$, which we have just shown is the $k$th column of $M$. We therefore have

$\langle e_j \vert M \vert e_k \rangle = \sum_l \langle e_j \vert_l M_{lk} = \langle e_j \vert_j M_{jk} + \sum_{l \ne j} \langle e_j \vert_l M_{lk}$

But by the definition of $\langle e_j \vert$ we have $\langle e_j \vert_j = 1$ and $\vert e_j \rangle_l = 0$ for $l \ne j$. So the above reduces to

$\langle e_j \vert_j M_{jk} + \sum_{l \ne j} \langle e_j \vert_l M_{lk} = 1 \cdot M_{jk} + \sum_{l \ne j} 0 \cdot M_{lk} = M_{jk}$

We thus have $\langle e_j \vert M \vert e_k \rangle = M_{jk}$.

## Quantum Country exercise 9

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 9. Show that for any matrix $M$ and vector $\vert \psi \rangle$ the following identity holds: $\Vert M \vert \psi \rangle \Vert^2 = \langle \psi \vert M^\dagger M \vert \psi \rangle$.

Answer: By definition we have $\Vert M \vert \psi \rangle \Vert^2 = \left( M \vert \psi \rangle \right)^\dagger M \vert \psi \rangle$. It was shown in the text that $\left( M \vert \psi \rangle \right)^\dagger = \vert \psi \rangle^\dagger M^\dagger$. By definition we also have $\langle \psi \vert = \vert \psi \rangle^\dagger$.

We then have

$\Vert M \vert \psi \rangle \Vert^2 = \left( M \vert \psi \rangle \right)^\dagger M \vert \psi \rangle = = \vert \psi \rangle^\dagger M^\dagger M \vert \psi \rangle = \langle \psi \vert M^\dagger M \vert \psi \rangle$

So we have shown that $\Vert M \vert \psi \rangle \Vert^2 = \langle \psi \vert M^\dagger M \vert \psi \rangle$ for any matrix $M$ and vector $\vert \psi \rangle$.

## Quantum Country exercise 8

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 8. Show that the matrices $Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}$ and $Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$ are unitary.

Answer: For $Y$ we have

$\begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}^\dagger \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} = \left( \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}^T \right)^* \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} = \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix}^* \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}$

$= \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} = \begin{bmatrix} -i^2 & 0 \\ 0 & -i^2 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$

For $Z$ we have

$\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}^\dagger \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$

So both $Y$ and $Z$ are unitary.

## Quantum Country exercise 7

This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 7. Find a matrix other than $I$, $X$, or $H$ that is unitary.

Answer: Both $I$ and $X$ have two zero entries and two entries with value 1, such that the 1 values end up multiplying each other to produce a 1 value in the resulting matrix $I^\dagger I$ or $X^\dagger X$.

This raises the possibility of having a matrix where the value $i$ ends up multiplying the value $-i$, since $i \cdot (-i) = -i^2 = -(-1) = 1$. Two possible candidate matrices with two entries with value $i$ are $\begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix}$ and $\begin{bmatrix} 0 & i \\ i & 0 \end{bmatrix}$.

We have

$\begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix}^\dagger \begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix} = \left( \begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix}^T \right)^* \begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix} = \begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix}^* \begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix}$

$= \begin{bmatrix} -i & 0 \\ 0 & -i \end{bmatrix} \begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix} = \begin{bmatrix} -i^2 & 0 \\ 0 & -i^2 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$

We also have

$\begin{bmatrix} 0 & i \\ i & 0 \end{bmatrix}^\dagger \begin{bmatrix} 0 & i \\ i & 0 \end{bmatrix} = \begin{bmatrix} 0 & -i \\ -i & 0 \end{bmatrix} \begin{bmatrix} 0 & i \\ i & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$

Consider also the matrix $\begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix}$. For it we have

$\begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix}^\dagger \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix} = \left( \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix}^T \right)^* \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix} = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}^* \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix}$

$= \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix} \begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix} = \begin{bmatrix} -i^2 & 0 \\ 0 & -i^2 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$

Finally, for the matrix $\begin{bmatrix} i & 0 \\ 0 & -i \end{bmatrix}$ we have

$\begin{bmatrix} i & 0 \\ 0 & -i \end{bmatrix}^\dagger \begin{bmatrix} i & 0 \\ 0 & -i \end{bmatrix} = \begin{bmatrix} -i & 0 \\ 0 & i \end{bmatrix} \begin{bmatrix} i & 0 \\ 0 & -i \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$

So $\begin{bmatrix} i & 0 \\ 0 & i \end{bmatrix}$, $\begin{bmatrix} 0 & i \\ i & 0 \end{bmatrix}$, $\begin{bmatrix} 0 & i \\ -i & 0 \end{bmatrix}$, and $\begin{bmatrix} i & 0 \\ 0 & -i \end{bmatrix}$ are all examples of unitary matrices other than $I$, $X$, or $H$.