Fredkin/CSWAP Gate

Definition¹

The following vector-valued Boolean function is referred to as a Fredkin Gate.

$$ F : \left\{ 0, 1 \right\}^{3} \to \left\{ 0, 1 \right\}^{3} $$

$$ F (a, b, c) = \Big(a, (\lnot a \land b) \lor (a \land c), (\lnot a \land c) \lor (a \land b) \Big) $$

• $\text{CSWAP}$ Gate is also known as.

Description

Introduced by Edward Fredkin, the Fredkin Gate swaps the remaining two values without altering the first input, if the first input is $1$. The specific computation is as follows.

$$ \begin{align*} F (0,0,0) &= (0, (\lnot 0 \land 0) \lor (0 \land 0), (\lnot 0 \land 0) \lor (0 \land 0)) = (0, 0 \lor 0, 0 \lor 0) = (0, 0, 0) \\ F (0,0,1) &= (0, (\lnot 0 \land 0) \lor (0 \land 1), (\lnot 0 \land 1) \lor (0 \land 0)) = (0, 0 \lor 0, 1 \lor 0) = (0, 0, 1) \\ F (0,1,0) &= (0, (\lnot 0 \land 1) \lor (0 \land 0), (\lnot 0 \land 0) \lor (0 \land 1)) = (0, 1 \lor 0, 0 \lor 0) = (0, 1, 0) \\ F (0,1,1) &= (0, (\lnot 0 \land 1) \lor (0 \land 1), (\lnot 0 \land 1) \lor (0 \land 1)) = (0, 1 \lor 0, 1 \lor 0) = (0, 1, 1) \\ F (1,0,0) &= (1, (\lnot 1 \land 0) \lor (1 \land 0), (\lnot 1 \land 0) \lor (1 \land 0)) = (1, 0 \lor 0, 0 \lor 0) = (1, 0, 0) \\ F (1,0,1) &= (1, (\lnot 1 \land 0) \lor (1 \land 1), (\lnot 1 \land 1) \lor (1 \land 0)) = (1, 0 \lor 1, 0 \lor 0) = (1, 1, 0) \\ F (1,1,0) &= (1, (\lnot 1 \land 1) \lor (1 \land 0), (\lnot 1 \land 0) \lor (1 \land 1)) = (1, 0 \lor 0, 0 \lor 1) = (1, 0, 1) \\ F (1,1,1) &= (1, (\lnot 1 \land 1) \lor (1 \land 1), (\lnot 1 \land 1) \lor (1 \land 1)) = (1, 0 \lor 1, 0 \lor 1) = (1, 1, 1) \\ \end{align*} $$

From the table, it is evident that $F$ is a reversible function and that composing $F$ twice results in an identity function.

$$ \operatorname{Id} = F \circ F $$

Furthermore, since $\left\{ F \right\}$ is functionally complete, $F$ is a universal gate.

Boolean Function	Symbol
$F$

Theorem

Assuming unrestricted use of projection and injection, the Fredkin Gate $F$ is a universal gate. In other words, $\left\{ F \right\}$ is functionally complete.

Proof

Theorem

The set of $\text{NOT}$ Gate and $\text{AND}$ Gate, $\left\{ \lnot, \land \right\}$, is functionally complete.

Following the theorem, demonstrating that projection, injection, and $F$ can appropriately represent $\text{NOT}$ and $\text{AND}$ concludes the proof.

• $\text{NOT}$ Gate

  $$ \lnot = p_{0} \circ p_{1} \circ F \circ \jmath_{2} \circ \imath_{1} $$

  Holds true. Since $\jmath_{2} \circ \imath_{1} (a) = (a, 0, 1)$, the following is obtained:

  $$ \begin{equation} F \circ \jmath_{2} \circ \imath_{1}(a) = F(a, 0, 1) = (a, a, \lnot a) \end{equation} $$

  To eliminate the first two values, take $p_{0} \circ p_{1}$, resulting in:

  $$ p_{0} \circ p_{1} \circ F \circ \jmath_{2} \circ \imath_{1} (a) = p_{0} \circ p_{1} (a, a, \lnot a) = \lnot a $$

  ※ Additionally, applying $p_{2}$ to $(1)$ yields a duplication function.

• $\text{AND}$ Gate

  $$ \land = p_{0} \circ p_{1} \circ F \circ \imath_{2} $$

  Holds true. Initially, $F \circ \jmath_{2} (a, b)$ is as follows:

  $$ \begin{align*} F \circ \jmath_{2} (a, b) = F(a, b, 0) &= (a, (\lnot a \land b) \lor (a \land 0), (\lnot a \land 0) \lor (a \land b)) \\ &= (a, (\lnot a \land b) \lor 0, 0 \lor (a \land b)) \\ &= (a, \lnot a \land b, a \land b) \end{align*} $$

  Therefore, taking $p_{0} \circ p_{1}$ results in:

  $$ p_{0} \circ p_{1} \circ F \circ \imath_{2} (a, b) = p_{0} \circ p_{1} (a, \lnot a \land b, a \land b) = a \land b $$

■

See Also

• $\text{AND}$ Gate
• $\text{OR}$ Gate
• $\text{NOT}$ Gate
• $\text{XOR}$ Gate
• $\text{NAND}$ Gate
• $\text{NOR}$ Gate
• $\operatorname{CNOT}$ Gate
• Toffoli Gate