Universal Reversible Logic with Fredkin and Toffoli Gates
Reversible computing allows computation without the loss of information, preventing the theoretical minimum energy dissipation described by Landauer’s Principle. The Toffoli gate and the Fredkin gate are 3-bit reversible logic gates that serve as fundamental building blocks for reversible and quantum computing. This article explains how each gate functions within the binary system, how their bijective input-output mappings preserve information, and how they can be configured to synthesize any standard Boolean logic operation to achieve computational universality.
Principles of Reversible Computing
Traditional binary logic gates like AND, OR, and NAND are irreversible because they take two input bits and produce one output bit. Because information is lost during computation, the original inputs cannot be reconstructed from the output.
A reversible logic gate must have an equal number of inputs and outputs (\(n \times n\)), forming a bijective (one-to-one and onto) mapping. This ensures that every unique input pattern produces a unique output pattern, allowing computations to run both forward and backward without information loss.
The Toffoli Gate (Controlled-Controlled-NOT)
The Toffoli gate, often called the CCNOT gate, operates on three binary inputs: two control bits (\(A, B\)) and one target bit (\(C\)).
Operation and Truth Table
The Toffoli gate leaves the control bits unchanged and inverts the
target bit if and only if both control bits are 1.
- Inputs: \((A, B, C)\)
- Outputs: \((A',
B', C')\) where:
- \(A' = A\)
- \(B' = B\)
- \(C' = C \oplus (A \land B)\) (\(\oplus\) denotes the XOR operation)
| \(A\) | \(B\) | \(C\) | \(A'\) | \(B'\) | \(C'\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
Achieving Universality
To prove universality, the Toffoli gate can reproduce a functionally complete set of Boolean logic operations (such as NOT, AND, and FAN-OUT) by setting fixed input values (ancilla bits):
- NOT Gate: Set \(A = 1\) and \(B = 1\). The output \(C'\) becomes \(C \oplus (1 \land 1) = \neg C\).
- AND Gate: Set \(C = 0\). The output \(C'\) becomes \(0 \oplus (A \land B) = A \land B\).
- FAN-OUT (Copy): Set \(B = 1\) and \(C = 0\). The output \(C'\) becomes \(A\), producing two copies of \(A\) (at \(A'\) and \(C'\)).
- NAND Gate: Set \(C = 1\). The output \(C'\) becomes \(1 \oplus (A \land B) = \neg(A \land B)\).
Because the NAND operation alone is universal, the Toffoli gate is universal for classical computation.
The Fredkin Gate (Controlled-SWAP)
The Fredkin gate operates on a control bit (\(C\)) and two data bits (\(I_1, I_2\)). It is a conservative logic
gate, meaning it preserves the total number of 0s and
1s from input to output.
Operation and Truth Table
If the control bit is 0, the data bits pass through
unchanged. If the control bit is 1, the data bits are
swapped.
- Inputs: \((C, I_1, I_2)\)
- Outputs: \((C', O_1,
O_2)\) where:
- \(C' = C\)
- \(O_1 = (\neg C \land I_1) \lor (C \land I_2)\)
- \(O_2 = (C \land I_1) \lor (\neg C \land I_2)\)
| \(C\) | \(I_1\) | \(I_2\) | \(C'\) | \(O_1\) | \(O_2\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Achieving Universality
The Fredkin gate achieves computational universality by synthesizing fundamental logic operations using fixed ancilla inputs:
- AND Gate: Set \(I_1 = A\), \(I_2 = 0\), and \(C = B\). The output \(O_2\) produces \(A \land B\).
- NOT Gate / FAN-OUT: Set \(I_1 = 0\) and \(I_2 = 1\). The output \(O_1\) produces \(C\), and \(O_2\) produces \(\neg C\).
- OR Gate: Set \(I_1 = 1\), \(I_2 = B\), and \(C = A\). The output \(O_1\) produces \(A \lor B\).
By providing AND, OR, NOT, and FAN-OUT operations, the Fredkin gate can construct any arbitrary combinatorial binary circuit while remaining entirely reversible and conservative.