2
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

The CNOT gate is definitely not the only non-trivial reversible gate on two input bits. For example, you could switch the order of inputs or the order of outputs. What Wikipedia means is that CNOT is the only non-trivial reversible gate up to some allowed operations, which consist of permuting the inputs and outputs, and applying reversible one-bit gates on the inputs and outputs.

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.

$\endgroup$
1
  • $\begingroup$ Thank you so much! This helps me a lot! $\endgroup$ Apr 20, 2021 at 23:57

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.