# Equivalence between quantum circuit: CNOT changes control and target qubit

It's know that the following two circuits are equal.

In fact, answers for this can be found on wikipedia, and on this website. However, I am looking for a more formal answer. I'd like to see the answer from the following calculations:

$$|x,y\rangle \to$$ $$(H \otimes H) \to \frac{1}{2}\sum_{i,j \in \{0,1\}}(-1)^{xi+yj}|i,j\rangle$$ $$\to (CNOT) \to \frac{1}{2}\sum_{i,j \in \{0,1\}}(-1)^{xi+yj}|i,i\oplus j\rangle$$ $$\to (H \otimes H) \to \frac{1}{4}\sum_{i,j,l,k \in \{0,1\}}(-1)^{xi+yj+li+k(i\oplus j)}|l,k\rangle$$

This somehow should be equivalent to $$= |x \oplus y, y \rangle$$

• you can turn it to operator and do calculation
– poig
Commented Jul 2, 2022 at 7:35
• Of course I know this. That's exactly what I am trying to avoid. :) Commented Jul 2, 2022 at 8:06

Your computations are correct. The last steps are: \begin{align*} &\frac14\sum_{i,j,k,l\in\{0,1\}}(-1)^{xi+yj+li+k(i\oplus j)}|l,k\rangle\\ ={}&\frac14\sum_{k,l\in\{0,1\}}\left(\sum_{i,j\in\{0,1\}}(-1)^{xi+yj+li+ki+kj}\right)|l,k\rangle\\ ={}&\frac14\sum_{k,l\in\{0,1\}}\underbrace{\left(\sum_{i\in\{0,1\}}(-1)^{i(x\oplus l\oplus k)}\right)}_{2\text{ if }x\oplus l\oplus k = 0\text{, }0\text{ otherwise}}\underbrace{\left(\sum_{j\in\{0,1\}}(-1)^{j(y\oplus k)}\right)}_{2\text{ if }y\oplus k = 0\text{, }0\text{ otherwise}}|l,k\rangle \end{align*} Thus, the only term in this sum which is non-zero is the one such that $$l=x\oplus k$$ and $$k=y$$, with "amplitude" $$4$$. All in all, the final state is $$|x\oplus y,y\rangle$$.