# Why is CNOT the only non-trivial reversible gate for two input bits?

The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function: $$00 \to 00 \\ 01 \to 01 \\ 10 \to 11 \\ 11 \to 10$$

I think I found a different non-trivial gate on two input bits: $$00 \to 01 \\ 01 \to 00 \\ 10 \to 10 \\ 11 \to 11$$ I think the matrix corresponding to this gate is $$\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix}$$ which is different from $$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{bmatrix}$$ and is also unitary.

• The usual rule is one question per post. Your questions don't seem to be directly related, so please separate them into different posts. Apr 18, 2021 at 5:58
• Ok. I changed it. Apr 19, 2021 at 1:34

If a two-input gate $$G$$ is reversible, then it is a permutation on $$00,01,10,11$$. By possibly negating the inputs (or the outputs), we can assume that $$G(00) = 00$$. By possibly switching the order of the inputs, we can assume that in $$G(01) < G(10)$$. We are left with three possibilities: $$00 \to 00 \quad 00 \to 00 \quad 00 \to 00 \\ 01 \to 01 \quad 01 \to 01 \quad 01 \to 10 \\ 10 \to 10 \quad 10 \to 11 \quad 10 \to 11 \\ 11 \to 11 \quad 11 \to 10 \quad 11 \to 01$$ The first possibility is the identity, which is trivial. The second possibility is CNOT. The third possibility is CNOT with outputs swapped.