Show that a $CZ$ gate can be implemented using a $CNOT$ gate and Hadamard gates

Show that a $$CZ$$ gate can be implemented using a $$CNOT$$ gate and Hadamard gates and write down the corresponding circuit.

Recall from Quantum Information Theory that $$Z=HXH$$. As $$CNOT$$ is a controlled-$$X$$ operation, we would expect that $$CZ= (I \otimes H)CNOT(I\otimes H)$$.

Why would we expect this form? Where does this come from?

Here is the CNOT gate:

$$CNOT = |0\rangle \langle 0|\otimes I + |1\rangle \langle 1| \otimes X$$

So:

$$(I \otimes H) CNOT (I \otimes H) = |0\rangle \langle 0|\otimes HH + |1\rangle \langle 1| \otimes HXH$$

If we will take into account $$HXH = Z$$ and $$HH = I$$, then:

$$(I \otimes H) CNOT (I \otimes H) = |0\rangle \langle 0|\otimes I + |1\rangle \langle 1| \otimes Z = CZ$$

Let's show that $$CNOT = |0\rangle \langle 0|\otimes I + |1\rangle \langle 1| \otimes X$$:

$$|0\rangle \langle 0|\otimes I + |1\rangle \langle 1| \otimes X = \begin{pmatrix}1&0 \\ 0&0 \end{pmatrix} \otimes\begin{pmatrix}1&0 \\ 0&1 \end{pmatrix} + \begin{pmatrix}0&0 \\ 0&1 \end{pmatrix} \otimes\begin{pmatrix}0&1 \\ 1&0 \end{pmatrix} = \\ =\begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \\ \end{pmatrix} + \begin{pmatrix} 0&0&0&0 \\ 0&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \\ \end{pmatrix} = \begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \\ \end{pmatrix} = CNOT$$

The form $$(I \otimes H)CNOT(I \otimes H)$$ just means that you have a control qubit whose state is left unchanged (applying the $$I$$ operator), and a target qubit whose state is operated with $$H$$, controlled-$$X$$ and $$H$$ again. This is actually a controlled-$$Z$$ operator applied to a two-qubit system.

In simple words:

• if a control qubit of CNOT is $$|0\rangle$$, $$I$$ is applied on target qubit. Since $$H^2=I$$, $$HIH=I$$ and nothing is done on the target qbubit
• if the control qubit of CNOT is $$|1\rangle$$, an operator $$HXH=Z$$ is applied on the target qubit.

Hence we have controlled $$Z$$.