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}\]