My Math Homework

Quantum Country exercise 16

Posted on October 19, 2021 by hecker

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.

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.

Posted in quantum country | Leave a comment

Quantum Country exercise 15

Posted on October 19, 2021 by hecker

Exercise 15. Fi.

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

Posted in quantum country | Leave a comment

Quantum Country exercise 14

Posted on October 19, 2021 by hecker

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

Posted in quantum country | Leave a comment

Quantum Country exercise 13

Posted on October 19, 2021 by hecker

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.

Posted in quantum country | Leave a comment

Quantum Country exercise 12

Posted on October 19, 2021 by hecker

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.

Posted in quantum country | Leave a comment

Quantum Country exercise 11

Posted on October 19, 2021 by hecker

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.

Posted in quantum country | Leave a comment

Quantum Country exercise 10

Posted on October 14, 2021 by hecker

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

Posted in quantum country | Leave a comment

Quantum Country exercise 9

Posted on October 13, 2021 by hecker

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

Posted in quantum country | Leave a comment

Quantum Country exercise 8

Posted on October 13, 2021 by hecker

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.

Posted in quantum country | Leave a comment

Quantum Country exercise 7

Posted on October 13, 2021 by hecker

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

Posted in quantum country | Leave a comment

My Math Homework

Quantum Country exercise 16

Quantum Country exercise 15

Quantum Country exercise 14

Quantum Country exercise 13

Quantum Country exercise 12

Quantum Country exercise 11

Quantum Country exercise 10

Quantum Country exercise 9

Quantum Country exercise 8

Quantum Country exercise 7

Archives

Meta