How to implement a reversible OR operator with a Fredkin gate ?


As also stated in the relevant Wikipedia page, you can do it by using the first two inputs (the control-bit and one of the target bits) as input for the reversible OR, and the third input bit fixed with the value 1. Then, the second output is what you want.

To better see this, write the general action of a Fredkin on an input as following: $$\begin{pmatrix}a\\b\\ c\end{pmatrix}\mapsto \begin{pmatrix} a \\ (a c)\oplus[(1\oplus a)b] \\ (a b)\oplus[(1\oplus a)c] \end{pmatrix}.$$ Note that this is just rewriting the action of the Fredkin algebraically.

Then, if you use as input $(a,b,1)$, you get

$$\begin{pmatrix}a\\b\\ 1\end{pmatrix}\mapsto \begin{pmatrix} a \\ a\oplus[(1\oplus a)b] \\ (a b)\oplus(1\oplus a) \end{pmatrix},$$ which is what you want as soon as you notice that $a \oplus b\oplus ab=a\,\operatorname{OR}\, b$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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