# Notes - Quantum Information HT24, Quantum gates

### Flashcards

The most common universal gate set is $\{\mathtt{CNOT}, H, T\}$. Can you define each?

- $\mathtt{CNOT} = \vert 0\rangle\langle 0 \otimes I + \vert 1\rangle\langle1 \vert \otimes X$
- $H = \vert +\rangle \langle 0 \vert + \vert -\rangle\langle 1 \vert $
- $T = P(\pi / 4) = \vert 0\rangle \langle 0 \vert + e^{i\pi / 4} \vert 1\rangle\langle 1 \vert $

Define the $\mathtt{CNOT}$ gate, first as the outer product of basis states, and then as a matrix in the computational basis.

Define the Pauli matrices.

How can you consider the quantum gates $Z$, $S$ and $T$ all as “the same thing”?

They are all phase gates. Define

\[P(\varphi) = |0\rangle \langle0| + e^{i\varphi} |0\rangle\langle0|\]Then

\[Z = P(\pi), S = P(\pi / 2), T = P(\pi /4)\]Can you define the quantum gate $H$ in terms of outer products of basis states, then as a matrix, and then say what this intuitively does?

This turns the computational basis into the Fourier basis,

\[\begin{aligned} |0\rangle &\mapsto |+\rangle \\\\ |1\rangle &\mapsto |-\rangle \end{aligned}\]Can you define the quantum gate $T$ in terms of outer products of basis states and then as a matrix?

Why is this quantum gate

\[T = |0\rangle \langle 0| + e^{i\pi / 4} |1\rangle\langle 1|\]
sometimes called the $\pi/8$ gate?

Because, up to global phase

\[T = e^{-\pi i / 8} |0\rangle \langle0| + e^{\pi i /8} |1\rangle\langle 1|\]How can you write the Hadamard gate

\[\begin{aligned}
H &= |0\rangle\langle +| + |-\rangle\langle 1| \\\\
&= \frac 1 {\sqrt 2}\begin{pmatrix}
1 & 1 \\\\
1 & -1
\end{pmatrix}
\end{aligned}\]
in terms of Pauli matrices (square roots are allowed)?

The Hadamard gate is a $\pi / 2$ rotation around the $Y$-axis, followed by a $\pi$ rotation about the $X$-axis, so

\[H = X Y^{\frac 1 2}\](Note that just $H = Y^\frac{1}{2}$ doesn’t work, despite the fact that $Y^\frac{1}{2} \vert 0\rangle = \vert +\rangle$, because applying the gate again gives $ \vert 1\rangle$, but $H^2 \vert 0\rangle = \vert 0\rangle$).

How could you write $\mathtt{SWAP}$ first in terms of Pauli matrices, and then as a matrix with respect to the computational basis?

How could you write the states $ \vert \Phi^+\rangle, \vert \Phi^-\rangle, \vert \Psi^{+}\rangle, \vert \Psi^{-}\rangle$ using the CNOT gate and qubits from $ \vert 0\rangle, \vert 1\rangle, \vert +\rangle, \vert -\rangle$?

How could you write the Pauli matrices $\{X, Y, Z\}$ in terms of gates from the standard gate set $\{\mathtt{CNOT}, H, T\}$?

How could you write the controlled-$Z$ gate ($CZ$) in terms of gates from the standard gate set $\{\mathtt{CNOT}, H, T\}$?

Note that since

\[\mathtt{CNOT} = |0\rangle \langle 0| \otimes I + |1\rangle\langle 1| \otimes X\]and that

\[Z = HXH, \quad HH = I\]we can just multiply both sides by $I \otimes H$:

\[(I \otimes H) \mathtt{CNOT} (I \otimes H) = \mathtt{CZ} = |0\rangle \langle 0| \otimes I + |1\rangle\langle 1| \otimes Z\]Suppose we have a boolean function $f : {0, \cdots, N - 1} \to {0, 1}$ and want to determine $x$ such that $f(x) = 1$ given a reduced quantum oracle $V _ f$ defined by

\[V_f | x\rangle := (-1)^{f(x)} |x\rangle \quad \forall x \in \\{0, \cdots, N-1\\}\]
Furthermore, suppose the number of $x$ such that $f(x) = 1$ is $S \ll N$. Grover’s search algorithm is then given by:

- Prepare the system in the Fourier basis state $e _ 0 = \frac{1}{\sqrt N} \sum^{N-1} _ {x = 0} \vert x\rangle$
- Apply the reduced oracle $V _ f$
- Apply the gate $W := 2 \vert e _ 0\rangle \langle e _ 0 \vert - I$
- Repeat steps 2 and 3 $K$ times, where $K$ is the closest integer to $\frac \pi 4 \sqrt{\frac N S} - \frac 1 2$.
- Measure the system in the computational basis

How can you implement the gate $W$ with gates from the set $\{\mathtt{CNOT}, H, T\}$ in the case where $N = 4$?

- Prepare the system in the Fourier basis state $e _ 0 = \frac{1}{\sqrt N} \sum^{N-1} _ {x = 0} \vert x\rangle$
- Apply the reduced oracle $V _ f$
- Apply the gate $W := 2 \vert e _ 0\rangle \langle e _ 0 \vert - I$
- Repeat steps 2 and 3 $K$ times, where $K$ is the closest integer to $\frac \pi 4 \sqrt{\frac N S} - \frac 1 2$.
- Measure the system in the computational basis

First of all, since $N= 4$, $ \vert e _ 0\rangle$ is $ \vert +\rangle \otimes \vert +\rangle$. So

\[W = 2(|+\rangle \otimes |+\rangle)(\langle+|\otimes \langle+|) - I \otimes I\]Then:

\[\begin{aligned} W &= 2(H \otimes H)(|0\rangle \otimes |0\rangle)(\langle 0| \otimes \langle 0|) (H \otimes H) - I \otimes I \\\\ &= (H \otimes H)(2(|0\rangle \otimes |0\rangle)(\langle 0| \otimes \langle 0|) - I\otimes I) (H \otimes H) \\\\ &= (H \otimes H) \left(\left(\begin{matrix} 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}\right) - \left(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right)\right) (H \otimes H) \\\\ &= (H \otimes H)\left(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1 \end{matrix}\right) (H \otimes H) \\\\ &= -(H \otimes H)\left(\begin{matrix} -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right) (H \otimes H) \\\\ &= (H \otimes H)\left(\begin{matrix} -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right) (H \otimes H) &&\text{up to phase} \end{aligned}\]Then we can notice that the matrix in the middle is very similar to the controlled-Z gate:

\[\left(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \end{matrix}\right)\]but the opposite way around. We can reverse the order of the diagonal on any matrix like this by applying $(X \otimes X)$ on both sides. This gives:

\[\begin{aligned} W = (H \otimes H) (X \otimes X) CZ(X \otimes X) (H \otimes H) \end{aligned}\]But how can we implement $CZ$ using standard gate sets? Multiply both sides of $CNOT$ by $I \otimes H$:

\[W = (H \otimes H) (X \otimes X) (I \otimes H)\mathtt{CNOT}(I \otimes H)(X \otimes X) (H \otimes H)\]To get rid of $X$, we can use the fact that $X = HT^4H$, to finally give:

\[\begin{aligned} W &= (H \otimes H) (HT^4H \otimes HT^4H) (I \otimes H)\mathtt{CNOT}(I \otimes H)(HT^4H \otimes HT^4H) (H \otimes H) \end{aligned}\]In the standard gate set $\{\mathtt{CNOT}, H, T\}$, $\mathtt{CNOT}$ has control on the first qubit. How could you implement $\mathtt{CNOT}$ but where the control is on the second qubit?

How can you implement $\mathtt{SWAP}$ using the standard gate set $\{\mathtt{CNOT}, H, T\}$?

where $\mathtt{CNOT} _ {12}$ is $\mathtt{CNOT}$ with control on the first qubit and $\mathtt{CNOT} _ {21}$ is $\mathtt{CNOT}$ with control on the second qubit. Then, since $\mathtt{CNOT} _ {21}$ can be written as

\[(H \otimes H) \mathtt{CNOT} (H \otimes H)\]we have

\[\mathtt{SWAP} = \mathtt{CNOT} (H \otimes H) \mathtt{CNOT} (H \otimes H) \mathtt{CNOT}\]