# Show that the two circuits are equivalent mathematically

This exercise wants me to prove the equivalence of the two circuits using their mathematical representations.

Circuit 1: Circuit 2: Circuit 1 (q1 CNOT q0) should be represented by $$I \otimes P_0 + X \otimes P_1$$. Circuit 2 (Hadamard q0 and q1, q0 CNOT q1, Hadamard q0 and q1) should be $$(H \otimes H)(P_0 \otimes I + P_1 \otimes X)(H \otimes H)$$.

I use the following identities $$P_0 + P_1 = I = P_{+} + P_{-}$$ $$X = P_{+} - P_{-}$$ $$Z = P_0 - P_1$$ $$P_{+} = HP_0H$$ $$P_{-} = HP_1H$$ where $$P_0, P_1, P_{+}, P_{-}$$ are $$|0\rangle\langle 0|$$, $$|1\rangle \langle 1|$$, $$|+\rangle \langle +|$$, and $$| - \rangle \langle - |$$ respectively.

I take circuit 1 and get this: $$I \otimes P_0 + X \otimes P_1$$ $$= (P_{+} + P_{-}) \otimes P_0 + (P_{+} - P_{-}) \otimes P_1$$ $$= P_{+} \otimes (P_0 + P_1) + P_{-} \otimes (P_0 - P_1)$$ $$= P_{+} \otimes I + P_{-} \otimes Z$$ $$= HP_0H \otimes I + HP_1H \otimes Z$$

Are my circuit representations correct to begin with? If so, should the Z operator be there? Any help would be appreciated.

Your derivation is correct and is just missing the final step:

\begin{align} \dots &= HP_0H \otimes I + HP_1H \otimes Z \\ &= HP_0H \otimes HH + HP_1H \otimes HXH \\ &= (H\otimes H) (P_0 \otimes I) (H\otimes H) + (H\otimes H) (P_1 \otimes X) (H \otimes H) \\ &= (H\otimes H) (P_0 \otimes I + P_1 \otimes X) (H \otimes H) \end{align}

where we used the identity $$HXH=Z$$ which is easy to check.

You can also just convert it to matrix representation and show that the two matrix are the same.

Circuit 1: This have $$q_1$$ as the controlled qubit and so it has the matrix representation as unitary matrix $$U_1$$: \begin{align} U_1 = CNOT_{q_1, q_0} &= I \otimes |0\rangle\langle0| + X \otimes |1 \rangle \langle 1| = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 \end{pmatrix} \end{align} where $$X = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$$ and $$|0\rangle\langle 0| = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$ and $$|1\rangle\langle 1| = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}$$

Circuit 2: Here we have $$U_2 = H\otimes H \cdot CNOT_{q_0, q_1} \cdot H \otimes H$$

where $$H = \dfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1\\ 1 & -1\\ \end{pmatrix}$$ and hence $$H \otimes H = \dfrac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\1 & -1 & -1 & 1 \end{pmatrix}$$. Therefore, $$U_2 =\begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\1 & -1 & -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\1 & -1 & -1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 \end{pmatrix}$$

Thus, $$U_1 = U_2$$.