# Showing the equivalence of two simple {NOT, CNOT} circuits

As a beginner, for exercise purpose, I’ve studied this two quantum circuits. They are equivalent, and for 2 qubits it’s easy to write the unitary transformation matrix. Looking for another method I wrote what follows, but I’m not sure about notation and, particularly, the last passage. So, I’m asking here if what I’ve written is admissible (maybe with some correction?). There are other methods?

You seem to have the basic idea. However, for a more formal way to approach the analysis, you might be interested in the following.$\def\ket#1{\lvert #1 \rangle}$

• The effect of the 'NOT' gate $X$ on standard basis states can be presented in terms of an explicit change to the bit value inside the Dirac notation, e.g.: $$X \,\ket t = \ket{t \oplus 1}$$ where $a \oplus b$ is the parity (i.e. the sum modulo 2) of a pair of bits $a,b \in \{0,1\}$.

• Using the fact that $a \oplus b$ is the sum mod 2 of a pair of bits $a,b \in \{0,1\}$,we know that $\oplus$ is commutative and associative, so that in particular $$(a \oplus b) \oplus c = (a \oplus c) \oplus b.$$

Using this, we may then describe your left-hand circuit as follows:

\begin{align} \ket{\psi_1} &= \ket{c} \otimes \ket{t} ; \\[2ex] \ket{\psi_2} &= X\ket{c} \otimes \ket{t} \\ &= \ket{c {\,\oplus\;\!} 1} \otimes \ket{t} ; \\[2ex] \ket{\psi_3} &= \ket{c {\,\oplus\;\!} 1} \otimes \ket{(c {\,\oplus\;\!} 1) {\,\oplus\;\!} t} \\ &= \ket{c {\,\oplus\;\!} 1} \otimes \ket{(c {\,\oplus\;\!} t) {\,\oplus\;\!} 1} \\ &= X\ket{c} \otimes X\ket{c {\,\oplus\;\!} t} . \end{align}

• Do you have a good reference for learning more about parity (specifically in regards to the fact of it being sum modulo 2)? – user820789 Jul 15 '18 at 22:11
• @meowzz: I am afraid I'm at a bit of a loss --- there is either very little or an enormous amount one can say. Parity simply is the sum modulo 2: even numbers are multiples of 2 and are therefore equivalent to zero mod 2, and any odd number is one more than an even number, and so are equivalent to one mod 2; the converses also hold pretty straightforwardly. Given this, for more about parity, one ought to learn a bit of number theory, and then consider the special case of arithmetic modulo 2. – Niel de Beaudrap Jul 15 '18 at 22:30
• How is parity used in QC? Is it correct that cnot is equivalent to xor which is equivalent to sum modulo 2? – user820789 Jul 15 '18 at 22:39
• @meowzz ‘Parity’, ‘sum modulo 2’, ‘xor’, and $\oplus$ all mean pretty much the same thing here: they take two bits and return one bit, mapping (0,0) and (1,1) to 0, and mapping (0,1) and (1,0) to 1. CNOT is slightly different—it takes two bits and returns two bits: $\operatorname{CNOT}(a, b) = (a, a \oplus b)$. CNOT is thus reversible, unlike XOR. But do follow Niel's advice about studying up on some number theory (and group theory). – Squeamish Ossifrage Jul 16 '18 at 0:54

The way that I like to do the maths is by using linearity to break things down, and be a bit more explicit. We don't have to keep general functional forms so long as we consider the action of the circuits on a basis of states. When one is using it with regards to a controlled-not, the most natural basis to use is to ensure you have the computational basis on the control qubit. For example, I can track what happens on the first circuit if I input either $|0\rangle$ or $|1\rangle$ on the first qubit. $$|0\rangle|t\rangle\rightarrow |1\rangle|t\rangle\rightarrow|1\rangle(X|t\rangle)\qquad |1\rangle|t\rangle\rightarrow |0\rangle|t\rangle\rightarrow|0\rangle|t\rangle$$ Meanwhile, for the second circuit, $$|0\rangle|t\rangle\rightarrow |0\rangle|t\rangle\rightarrow|1\rangle(X|t\rangle)\qquad |1\rangle|t\rangle\rightarrow |1\rangle(X|t\rangle)\rightarrow|0\rangle|t\rangle$$ Both circuits give the same outputs for a complete basis of states, so they must be the same unitaries.

• He is already using linearity, given that he is only considering the action on the standard basis. He is just using variables to represent more than one standard basis at once (as you are also doing, with your variable $t$). – Niel de Beaudrap Jul 16 '18 at 9:21

You can also use the definition of XOR in the following way: $c\oplus t = c'.t + c.t'$ (where the primes mean not)

$\implies (c\oplus t)' = (c'.t + c.t')'$

Now using De Morgan's rule, $(c'.t + c.t')' = (c+t').(c'+t) = c't'+ct$

Which can be seen as being the same as $c'\oplus t$

• This is almost on topic, but seems to be a remark about XOR in particular rather than anything specific to the circuits he's looking at... – Niel de Beaudrap Jul 16 '18 at 9:21
• The example chosen here is exactly the one that corresponds to the circuit given. It was asked if there were alternative ways to go about the problem, and I seem to have answered that. – user3518839 Jul 16 '18 at 12:31