For the following circuit that swap two qubits enter image description here

The sequence of gates is said to have the following sequence of effects on a computational basis state |a, b> enter image description here where all additions are done modulo 2.

On the 2nd and 3rd line, it's shown that $a ⊕ (a ⊕ b) = b$ and $(a ⊕ b) ⊕ b = a$, however, I have trouble understanding why this holds true.

  • 3
    $\begingroup$ Hi Cheryl, I'm not sure I understand. Are you having trouble with the addition modulo 2 part? Have you tried to put some numbers in place of $a$ and $b$ to see what result you get, just as a sanity check? how many residue classes are there in the set $\mathbb{Z}/2\mathbb{Z}$ of integers modulo 2? $\endgroup$ Aug 5 '21 at 1:25
  • 3
    $\begingroup$ @Cheryl, do you know what "modulo 2" means? :-) If so, consider what $x+x$ is modulo 2. If not, check out modulo operation. $\endgroup$ Aug 5 '21 at 1:32
  • 3
    $\begingroup$ I’m voting to close this question because it is not about quantum computing. The question is about modular arithmetic and so belongs on MSE. $\endgroup$ Aug 5 '21 at 1:33
  • $\begingroup$ I would disagree. The answer to the question is certainly one of modular arithmetic, but it is a fair question to ask in the context of quantum computing, and one whose answer may prove helpful to beginners. $\endgroup$
    – jecado
    Aug 5 '21 at 4:09
  • 1
    $\begingroup$ The answer may prove helpful to beginners outside of quantum computing, too. It would be easier to find on MSE. $\endgroup$ Aug 5 '21 at 5:49

First note that the location of the parentheses is chosen to make clear the action of the CNOT gate. For example, the second CNOT gate in the circuit leaves unchanged the control state $|a\oplus b\rangle$, but adds its value (modulo 2) to the target state $|a\rangle$, yielding $|a\oplus(a\oplus b)\rangle$.

Second, note that addition modulo 2 is associative (just like regular addition) meaning that the location of the parentheses can be rearranged. For example, $|a\oplus(a\oplus b)\rangle=|(a\oplus a)\oplus b\rangle$.

Third, apply the identities $x\oplus x=0$ and $0\oplus x=x$. For example, $|(a\oplus a)\oplus b\rangle=|0\oplus b\rangle =|b\rangle$.


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