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

enter image description here https://i.sstatic.net/BRKVW.png

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

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

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.