# Nielsen and Chuang -- Chapter 4

Updated on January 11, 2019

### (4.1) Find the points on the Bloch sphere which correspond to the normalized eigenvectors of the different Paul matrices.

Recall that, from Exercise 2.11, $X$ has eigenvalues $\pm 1$ with respective eigenvectors

$\Big\{ \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix}, \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix} \Big\}$

Similarly, $Y$ has eigenvalues $\pm 1$ with respective eigenvectors

$\Big\{ \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ i \end{bmatrix} , \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -i \end{bmatrix} \Big\}$

Finally, $Z$ has eigenvalues $\pm 1$ with respective eigenvectors

$\Big\{ \begin{bmatrix} 1 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 1 \end{bmatrix} \Big\}$

First, we solve for $X$.

$\Big\{ \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix}, \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix} \Big\} \iff \{ \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) , \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) \}$

So, for $\frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$, we have that $\cos(\theta / 2) = \frac{1}{\sqrt{2}}$. Hence, $\theta = \pi / 2$. Now, $e^{i\phi} \sin (\theta / 2) = e^{i \phi} / \sqrt{2} = 1 / \sqrt{2}$. Hence, $\phi = 0$.

Similarly, for the second eigenvector, $\theta = \pi / 2$ but $\phi = - \pi$.

Therefore, for the first eigenvector,

$(\cos \phi \sin \theta , \sin \phi \sin \theta, \cos \theta) = (\cos (0)\sin (\pi / 2) , \sin (0)\sin (\pi / 2) , \cos (\pi / 2) ) \\ = (1, 0, 0)$

And for the second we have,

$(\cos (\pi)\sin (\pi / 2) , \sin (\pi)\sin (\pi / 2) , \cos (\pi / 2) ) \\ = (-1, 0, 0)$

Similarly, we find the Bloch vectors $(0, \pm 1, 0)$ for $Y$ and $(0, 0, \pm 1)$ for $Z$.

### (4.2) Let $x \in \RR$ and $A$ be a matrix that satisfies $A^2 = I$. Show that

$\exp(i A x) = \cos(x) I + i \sin(x) A$

From the power series definition of $e^{z}$, we have that

$\exp(i A x) = \sum_{n=0}^\infty \frac{(iAx)^n}{n!} \\ = \sum_{n=0}^\infty \frac{(iAx)^{2n}}{(2n)!} + \sum_{n=0}^\infty \frac{(iAx)^{2n+1}}{(2n+1)!} \\ \sum_{n=0}^\infty \frac{(iAx)^{2n}}{(2n)!} = \sum_{n=0}^\infty \frac{i^{2n}A^{2n}x^{2n}}{(2n)!} \\ = \sum_{n=0}^\infty \frac{(-1)^{2n} I x^{2n}}{(2n)!} \\ = I \sum_{n=0}^\infty \frac{(-1)^{2n} x^{2n}}{(2n)!} = \cos(x)I \\ \sum_{n=0}^\infty \frac{(iAx)^{2n+1}}{(2n+1)!} = \sum_{n=0}^\infty \frac{i^{2n+1}A^{2n+1}x^{2n+1}}{(2n+1)!} \\ = \sum_{n=0}^\infty \frac{i(-1)^{2n+1}Ax^{2n+1}}{(2n+1)!} \\ = iA \sum_{n=0}^\infty \frac{(-1)^{2n+1}x^{2n+1}}{(2n+1)!} = i\sin(x) A$

$X, Y, Z$ give rise to three useful classes of unitary matrices when they are exponentiated, the rotation operators about $\hat{x}$, $\hat{y}$, and $\hat{z}$,

$R_x(\theta) \equiv e^{-i \theta X / 2} \\ R_y(\theta) \equiv e^{-i \theta Y / 2} \\ R_z(\theta) \equiv e^{-i \theta Z / 2}$

We can use exercise 4.2 to write the above equations more conveniently.

### (4.3) Show that, up to a global phase, the $\pi /8$ gate satisfies $T = R_z(\pi /4)$.

Note that

$T = \begin{bmatrix}1 & 0 \\ 0 & \exp(i\pi / 4) \end{bmatrix} = \exp(i\pi / 8)\begin{bmatrix} \exp(-i \pi / 8) & 0 \\ 0 & \exp(i \pi / 8) \end{bmatrix}$

Now, using the definition of $R_z$,

$e^{-i Z \frac{\pi}{8}} = \cos(-\pi/8) I + i\sin (-\pi / 8)Z \\ = \cos(\pi/8) I - i\sin (\pi / 8)Z \\ = \begin{bmatrix} \cos(\pi / 8) - i \sin (\pi / 8) & 0 \\ 0 & \cos(\pi/8) + i \sin (\pi / 8) \end{bmatrix} \\ = \begin{bmatrix} \exp(-i \pi / 8) & 0 \\ 0 & \exp(i \pi / 8) \end{bmatrix} \\$

### (4.4) Express the Hadamard gate $H$ as a product of $R_x$ and $R_z$ rotations and $e^{i \phi}$ for some $\phi$.

We’ve discussed a procedure for expressing $H$ as a product of rotations on the Bloch sphere, by considering its actions on a basis of the Bloch sphere. We showed that $R_x(-\pi / 2)R_z(-\pi / 2)R_x(-\pi / 2)$ suffices. We can verify this result a second way by considering the respective rotation matrices.

We know that $H = \frac{1}{\sqrt{2}} (X + Z)$. Furthermore,

$R_x(-\pi / 2) = \begin{bmatrix} \cos(\pi / 4) & i\sin(\pi / 4) \\ i\sin(\pi / 4) & \cos(\pi / 4) \end{bmatrix} \\ = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & i \\ i & 1 \end{bmatrix} = \frac{1}{\sqrt{2}}( I + iX) \\ R_z(-\pi / 2) = \begin{bmatrix} \cos(\pi / 4) + i\sin(\pi / 4) & 0 \\ 0 & \cos(\pi / 4) - i\sin (\pi / 4) \end{bmatrix} \\ = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 + i & 0 \\ 0 & 1-i \end{bmatrix} = \frac{1}{\sqrt{2}}( I + iZ)$

We’ll use that

$XZ = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix} \begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix} \\ = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} = iY \\ ZX = \begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix} \\ = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} = -iY \\ \implies XZ + ZX = 0 \\ \implies XZX + ZX^2 = 0 \\ \implies XZX = -Z$

Note that the above is simply showing that the anti-commutator of $X$ and $Z$, ${ X , Z} = 0$. This holds for any pair of distinct Pauli matrices (Exercise 2.41).

Hence,

$\frac{1}{2\sqrt{2}}( I + iX)( I + iZ)( I + iX) = \frac{1}{2\sqrt{2}}[I + iX + iZ + i^2ZX + iX + i^2X^2 + i^2XZ + i^3XZX ]\\ = \frac{1}{2\sqrt{2}}[I + iX + iZ - ZX + iX - I - XZ + i^3 XZX] \\ = \frac{1}{2\sqrt{2}}[i (X + Z) + iX -i XZX ]\\ = \frac{1}{2\sqrt{2}}[i(X + Z) + iX + iZ ]\\ = \frac{1}{\sqrt{2}}[i(X + Z)]$

which gives the Hadamard transform with phase $e^{i0}$.

### (4.5) Prove that $(\hat{n} \cdot \hat{\sigma} ) ^2 = I$, and use this to verify the following equation

$R_n(\theta) \equiv \exp(-i \theta n \cdot \sigma / 2) = \cos(\theta /2) I - i \sin(\theta / 2) (n_x X + n_y Y + n_z Z)$

Evidently, $\hat{n} \cdot \hat{\sigma} = (n_x X + n_y Y + n_z Z)$ so, recalling that distinct Pauli matrices anti-commute,

$(n_x X + n_y Y + n_z Z)^2 = n_x^2X^2 + n_xn_y XY + n_x n_z XZ + n_xn_y YX + n_y^2 Y^2 + n_yn_z YZ + n_x n_z ZX + n_y n_z ZY + n_z Z^2 \\ = (n_x^2 + n_y^2 + n_z^2)I + n_xn_z(XZ + ZX) + n_yn_z (YZ + ZY) + n_x n_y (XY + YX) \\ = (n_x^2 + n_y^2 + n_z^2)I = I$

because $\hat{n}$ is a unit vector.

Therefore, using Exercise 4.2 (Nielsen & Chuang), if we let $A = \hat{n} \cdot \hat{\sigma}$, then the result follows directly.

### (4.7) Show that $XY X = −Y$ and use this to prove that $XR_y(\theta)X = R_y(-\theta)$.

From above, we have that distinct Pauli matrices anti-commute. Furthermore, the Pauli matrices are hermitian and unitary $\implies$ $\sigma_i^2 = 0, i \in {x, y, z }$. Hence,

$XY + YX = 0 \\ XYX + YX^2 = 0 \\ XYX + Y =0 \\ XYX = -Y$

So,

$XR_y(\theta)X = X\big[\cos(\theta/2)I - i\sin(\theta / 2) Y\big]X \\ = \cos(\theta/2)X^2 -i\sin(\theta/2)XYX \\ = \cos(\theta/2)I + i \sin(\theta /2) Y \\ = \cos(-\theta/2)I - i \sin(-\theta /2) Y \\ = R_y(-\theta)$

using that $\cos(-x) = \cos(x), \sin(-x) = -\sin(x)$.

### (4.12) Give $A, B, C$, and $\alpha$ for the Hadamard gate.

Using Lemma 4.12 (Nielsen & Chuang) above we can solve, assuming $\gamma = \pi / 2$, $$H = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} e^{i(\alpha - \beta / 2 - \delta / 2)} & -e^{i (\alpha - \beta /2 + \delta / 2)} \\ e^{i(\alpha + \beta / 2 - \delta / 2)} & e^{i (\alpha + \beta /2 + \delta / 2)} \end{bmatrix} \\ \alpha - \beta / 2 - \delta / 2 = 0 \\ \alpha - \beta /2 + \delta / 2 = \pi \\ \alpha + \beta / 2 - \delta / 2 = 0 \\ (\alpha + \beta /2 + \delta / 2) = \pi \\ \implies \alpha = \pi / 2, \beta = 0, \delta = \pi$$

So, the proof of Corollary 4.2 in Nielsen & Chuang tells us to set

$A = R_z (\beta)R_y(\gamma / 2) \\ = R_z (0)R_y(\pi / 4) \\ = \begin{bmatrix} \cos(\pi / 8) & -\sin(\pi / 8) \\ \sin(\pi / 8) & \cos(\pi / 8) \end{bmatrix}\\ B = R_y(-\gamma/2)R_z(- (\delta+\beta)/2)\\ = R_y(- \pi/4)R_z(- \pi/2)\\ = \begin{bmatrix} \cos(\pi / 8) & \sin(\pi / 8) \\ -\sin(\pi / 8) & \cos(\pi / 8) \end{bmatrix} \begin{bmatrix} e^{i\pi / 4} & 0 \\ 0 & e^{- i\pi / 4} \end{bmatrix}\\ C = R_z((\delta - \beta)/2)\\ = R_z(\pi /2) \\ = \begin{bmatrix} e^{i\pi / 4} & 0 \\ 0 & e^{- i\pi / 4} \end{bmatrix}\\$

and $\alpha$ remains set $\alpha = \pi / 2$.

### (4.16)

For the first circuit, we consider action on the computational basis.

$\ket{x_1}\ket{x_2 } \rightarrow \ket{x_1}H\ket{x_2} = (I \otimes H) \ket{x_1}\ket{x_2 }$

Now, given that $H = \begin{bmatrix} 1 & 1 \ 1 & -1\end{bmatrix}$ w.r.t the computation basis, then

$(I \otimes H) = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 \end{bmatrix}$

Similarly, for the second circuit we have

$(H \otimes I) = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix}$

### (4.17)

Construct a CNOT gate from one controlled-$Z$ gate, that is, the gate whose action in the computational basis is specified by the unitary matrix

$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix}$

and two Hadamard gates, specifying the control and target qubits.

Recall that, in terms of the computational basis, the action of the CNOT is given by $\ket{c}\ket{t} \rightarrow \ket{c} \ket{t \oplus c}$ and that $Z = \begin{bmatrix} 1 & 0 \ 0 & -1 \end{bmatrix}$.

We construct our algorithm by first making the observation that $H\ket{+} = \ket{0}$ and $H\ket{-} = \ket{1}$. Hence, beginning with state $\ket{c}\ket{t}$ we can initially apply $H$ to $\ket{t}$. Now, using the control-$Z$ gate with $\ket{c}$ as the control and $H\ket{t}$ as the target, we have two cases:

(1) If $\ket{c = 1}$, then the second qubit will swap either from $\ket{+}$ to $\ket{-}$ or vis versa. Therefore, we can apply another Hadamard to the second qubit and have $\ket{t \oplus c}$ at the second qubit, as expected. The first qubit is unaltered, as expected.

(2) If $\ket{c = 1}$, then the second qubit will remain unchanged. Hence, if we apply another Hadamard to the second qubit, then $\ket{t}$ is recovered since $H^2 = I$. So, we have the expected behavior.

In summary, we have the circuit, beginning with state $\ket{c}\ket{t}$:

(1) Apply $H$ to the second qubit

(2) Controlled-$Z$ with the first qubit as the control and second as the target

(3) Apply $H$ to the second qubit.

From the next exercise, we’ll see that it didn’t actually matter whether we used the first or second qubit as control/target:

### (4.18)

We simply prove the statement for the computational basis.

(1) $\ket{0}\ket{0}$: Both circuits give the identity transform since they are conditioned on a qubit which is $\ket{0}$, in either case.

(2) $\ket{1}\ket{0}$: The first circuit is conditioned on $\ket{1}$, so it applies $Z$ to $\ket{0}$ which gives $\ket{0}$. Hence, we have $\ket{1}\ket{0}$. The second circuit is conditioned on $\ket{0}$, so we have the identity transform which gives $\ket{1}\ket{0}$, similarly.

(3) $\ket{0}\ket{1}$: By symmetry, we have the same outcome as in (2).

(4) $\ket{1}\ket{1}$: The first circuit is conditioned on the first $\ket{1}$, so it applies $Z$ to the second qubit which gives $-\ket{1}\ket{1}$. Similarly, the second circuit gives $-\ket{1}\ket{1}$.

### (4.19) The CNOT gate is a simple permutation whose action on a density matrix $\rho$ is to rearrange the elements in the matrix. Write out this action explicitly in the computational basis.

$\ket{00}\bra{00} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ \ket{01}\bra{01} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\\ \ket{10}\bra{10} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ \ket{11}\bra{11} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Now,

$C_1(X)\ket{00} = \ket{00} \\ C_1(X)\ket{01} = \ket{01} \\ C_1(X)\ket{10} = \ket{11} \\ C_1(X)\ket{11} = \ket{10}$

Hence, the permutation matrix acting on the computational basis as

$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$

satisfies this permutation.

### (4.20)

Consider action on $\ket{c}\ket{t}$ by the circuit on the LHS. The action of this circuit is given by $(H \otimes H) C^1(X)\ket{c}\ket{t} (H \otimes H)$ using $c$ as the control and $t$ as the target for the controlled operation. So, in Exercise 4.17, we showed that we can decompose $C^1(X)$ as $HC^1(Z)H$ using the same control and target as used for $C^1(X)$ originally, and with the $H$ transforms acting on the target qubit. Hence, we can rewrite action by the LHS circuit as $(H \otimes H) (I \otimes H) C^1(Z)\ket{c}\ket{t} (I \otimes H) (H \otimes H) = (H \otimes I) C^1(Z)\ket{c}\ket{t} (H \otimes I)$.

Similarly, for the circuit on the RHS, action on $\ket{c}\ket{t}$ is given by $C^1(X)\ket{c}\ket{t}$ where in this case $t$ is the control and $c$ is the target. Hence, using the same result, we can rewrite this as $(H \otimes I) C^1(Z)\ket{c}\ket{t} (H \otimes I)$ with $t$ as control and $c$ as target. Finally, using Exercise 4.18, we can swap which qubits we regard as control/target in a controlled-$Z$ operation. Hence, we have the action $(H \otimes I) C^1(Z)\ket{c}\ket{t} (H \otimes I)$ with $c$ as control and $t$ as target, as in the LHS.

Now, using that $H^2 = I$, we note that the identity given by the circuit is equivalent to $C^1(X) (H \otimes H)\ket{c}\ket{t} = C^1(X) \ket{t}\ket{c} (H \otimes H)$ (applying $H \otimes H$ to the end of both circuits). Hence, this directly gives the effect of CNOT on the basis $\ket{\pm}$.