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.


\[\begin{aligned} \mathtt{CNOT} &= |0\rangle\langle 0 \otimes I + |1\rangle\langle1| \otimes X \\\\ &= \begin{pmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \end{pmatrix} \end{aligned}\]

Define the Pauli matrices.


\[\begin{aligned} X &= \begin{pmatrix} 0 & 1 \\\\ 1 & 0 \end{pmatrix} \\\\ Y &= \begin{pmatrix} 0 & -i \\\\ i & 0 \end{pmatrix} \\\\ Z &= \begin{pmatrix} 1 & 0 \\\\ 0 & -1 \end{pmatrix} \\\\ \end{aligned}\]

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?


\[\begin{aligned} H &= |0\rangle\langle +| + |-\rangle\langle 1| \\\\ &= \frac 1 {\sqrt 2}\begin{pmatrix} 1 & 1 \\\\ 1 & -1 \end{pmatrix} \end{aligned}\]

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?


\[\begin{aligned} T &= |0\rangle \langle 0| + e^{i\pi / 4} |1\rangle\langle 1| \\\\ &= \begin{pmatrix} 1 & 0 \\\\ 0 & e^{\pi i /4} \end{pmatrix} \end{aligned}\]

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?


\[\frac{I \otimes I + X \otimes X + Y \otimes Y + Z \otimes Z}{2}\] \[\begin{aligned} \begin{pmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \end{pmatrix} \end{aligned}\]

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


\[\begin{aligned} \mathtt{CNOT}|+\rangle \otimes |0\rangle &= |\Phi^+\rangle \\\\ \mathtt{CNOT}|-\rangle \otimes |0\rangle &= |\Phi^-\rangle \\\\ \mathtt{CNOT}|+\rangle \otimes |1\rangle &= |\Psi^+\rangle \\\\ \mathtt{CNOT}|-\rangle \otimes |1\rangle &= |\Psi^-\rangle \\\\ \end{aligned}\]

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


\[\begin{aligned} &Z = T^4 \\\\ &X = HZH = HT^4 H \\\\ &Y = iXZ = iHT^4 HT^4 \end{aligned}\]

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:

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


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?


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

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


\[\mathtt{SWAP} = \mathtt{CNOT}_{12} \mathtt{CNOT}_{21}\mathtt{CNOT}_{12}\]

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

Proofs




Related posts